我在咨询机构工作,大部分时间都在客户所在地.因此,我很少见到我的同事.为了更好地了解彼此,我们将安排一个晚宴.将有许多小桌子,所以人们可以聊天.为了在聚会期间与尽可能多的不同的人交谈,每个人都必须在某个时间间隔(例如每小时)切换一次.
如何编写创建表切换计划的程序？只是给你一些数字; 在这种情况下,将有大约40人,每张桌子最多可以有8个人.但是,算法当然需要是通用的
我有特定范围内的数字(通常从0到1000左右).算法从该范围中选择一些数字(大约3到10个数字).这种选择经常进行,我需要检查是否已经选择了所选数字的排列.
例如,一步选择[1, 10, 3, 18]另一步,[10, 18, 3, 1]然后第二选择可以被丢弃,因为它是一种置换.
我需要非常快速地进行检查.现在我把所有数组都放在一个hashmap中,并使用一个自定义哈希函数:只需要总结所有元素,所以1 + 10 + 3 + 18 = 32,还有10 + 18 + 3 + 1 = 32.对于equals,我使用bitset来快速检查元素是否在两个集合中(我在使用bitset时不需要排序,但它只在数字范围已知且不太大时才有效).
这样可以正常工作,但是可以产生大量冲突,因此很常调用equals()方法.我想知道是否有更快的方法来检查排列？
排列是否有任何好的哈希函数？
UPDATE
我做了一个基准测试:生成0到6范围内的所有数字组合,以及数组长度1到9.有3003种可能的排列,并且应该在这么多不同的哈希值附近生成一个好的哈希值(我使用32位数字)对于哈希):
所以abc的哈希值可以非常快速地计算出来并且比其他所有哈希值都要好得多.谢谢!
PS:我不想在不需要时对值进行排序,因为这会变得太慢.
我在一个访谈网站上遇到了这个问题 - 我们给了4个数字说n1,n2,n3,n4.我们可以按任意顺序放置它们,我们可以在它们之间使用数学运算符+, - ,*,/来得到最终结果为24.为此编写一个算法 - 它将需要4个数字并返回false或true结果24可以任意组合.可以多次使用相同的运算符.
其中一种方法是 -
这种解决方案是强力的,不是最佳解决方案.我认为使用二叉搜索树可能有更好的解决方案.
手头的问题是:
给出一个字符串.在按字典顺序排列的所有排列中列出其排名.
这个问题可以用数学方法尝试,但我想知道是否还有其他一些算法来计算它？
此外,如果我们必须按顺序存储所有字符串排列,我们如何有效地生成它们(以及复杂性是多少).什么是用于存储排列的良好数据结构,并且对于检索也是有效的？
编辑
感谢排列生成部分的详细解答,有人还可以提出一个好的数据结构吗？我只能想到树木.
说我有一组数字[0, ....., 499].目前正在使用C++顺序生成组合std::next_permutation.作为参考,我提取的每个元组的大小是3,所以我返回顺序结果,如[0,1,2], [0,1,3], [0,1,4], ... [497,498,499].
现在,我想并行化这个代码所在的代码,因此这些组合的顺序生成将不再起作用.是否存在用于计算ith500个数字中的3个组合的现有算法？
我想确保每个线程,无论它获得的循环迭代如何,都可以根据迭代的内容计算一个独立的组合i.因此,如果我想要i=38在线程1中进行组合,我可以计算[1,2,5]同时i=0在线程2中进行计算[0,1,2].
编辑下面的陈述是无关紧要的,我把自己搞砸了
我已经研究过使用阶乘法从左到右缩小每个元素的算法,但我不能将它们用作500!肯定不适合记忆.有什么建议？
我正在尝试学习C++,并尝试解决一个问题,在这个步骤中给出了许多步骤以及可以采用的步骤的数量,给出了爬上台阶的可能方法的所有排列.因此,例如,如果有5个步骤可以攀爬,我可以一次向上移动1步,一次向上移动2步,或者一次向上移动3步,我需要打印出1,2和3的所有排列,加起来5: [1, 1, 1, 1, 1],[1, 1, 1, 2]....
我开始使用这段代码(它还没有完成),但是我收到了这个错误:
Undefined symbols for architecture x86_64:
"_num_steps(int, std::__1::vector<int, std::__1::allocator<int> >, std::__1::vector<std::__1::vector<int, std::__1::allocator<int> >, std::__1::allocator<std::__1::vector<int, std::__1::allocator<int> > > >, std::__1::vector<std::__1::vector<int, std::__1::allocator<int> >, std::__1::allocator<std::__1::vector<int, std::__1::allocator<int> > > >)", referenced from:
num_steps(int, std::__1::vector<int, std::__1::allocator<int> >) in num_steps-FTVSiK.o
ld: symbol(s) not found for architecture x86_64
我真的不明白我做错了什么.如果我能得到一些帮助,我会很感激.谢谢!
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
//prototypes
void _num_steps(int amount, vector<int> possible_steps, vector<vector<int>> steps_list, vector<vector<int>> result);
int sum(vector<int> steps_list);
void num_steps(int …如何随机洗牌以使所有元素都不在其原始位置？
换句话说,给定一个A包含不同元素的列表,我想生成B它的排列
n,a[n] != b[n]例如
a = [1,2,3,4]
b = [4,1,2,3] # good
b = [4,2,1,3] # good
a = [1,2,3,4]
x = [2,4,3,1] # bad
我不知道这种排列的正确术语(它是"总"吗？)因此很难用谷歌搜索.正确的术语似乎是"紊乱".
我正在准备采访,我正在努力记住Heap的算法:
procedure generate(n : integer, A : array of any):
if n = 1 then
output(A)
else
for i := 0; i < n; i += 1 do
generate(n - 1, A)
if n is even then
swap(A[i], A[n-1])
else
swap(A[0], A[n-1])
end if
end for
end if
该算法非常着名,可以生成排列.它简洁快速,与代码密切配合,生成组合.
问题是:我不喜欢记住事情,我总是试图让概念在以后"推断"算法.
这个算法真的不直观,我找不到解释它如何对我自己起作用的方法.
有人可以告诉我为什么以及如何在生成排列时该算法按预期工作？
我有一个包含一些元素的列表,并希望迭代所有可能的方法将此列表分成两个列表.我的意思是所有组合,所以顺序无关紧要(即元素1和3可以在一个列表中,元素2在另一个列表中).目前我这样做,facs我的初始列表在哪里:
patterns = []
for i in range(2**(len(facs)-1)):
pattern = []
for j in range((len(facs)-1)):
pattern.append(i//(2**j)%2)
patterns.append(pattern)
for pattern in patterns:
l1 = [facs[-1]]
l2 = []
for i in range(len(pattern)):
if pattern[i] == 1:
l1.append(facs[i])
else:
l2.append(facs[i])
所以我基本上创建了一个长度列表,2^(len(facs)-1)并用每个可能的1和0组合填充它.然后我'覆盖'每个模式facs,除了最后一个元素facs总是在l1,因为我会得到每个结果两次,因为我处理两个相同的列表,无论列表是什么l1或l2.
是否有更快更优雅(更短/更pythonic)的方式来做到这一点？
我想用种子np.random.permutation,比如
np.random.permutation(10, seed=42)
我收到以下错误:
"permutation() takes no keyword arguments"
我该怎么办呢？谢谢.
permutation ×10
algorithm ×5
combinations ×3
python ×3
c++ ×2
random ×2
c++11 ×1
hash ×1
list ×1
numpy ×1
performance ×1
pseudocode ×1
string ×1
vector ×1