所以我需要一种算法来生成除循环旋转之外的数字列表的所有排列(例如[1,2,3] == [2,3,1] == [3,1,2]).
如果序列中至少有一个唯一编号,则相当简单,取出该唯一编号,生成剩余编号的所有排列(但对“标准”排列算法进行少量修改)并将唯一编号添加到前方.
def permutations(done,options)
permuts = []
seen = []
for each o in options
if o not in seen
seen.add(o)
permuts += permutations(done+o,options.remove(o))
return permuts
仅在选项中使用每个唯一编号一次意味着您不会获得322两次.
当没有唯一元素时,例如,该算法仍然输出旋转.对于[1,2],它将输出[1,[1,1]和[1,前两个是循环旋转.
那么是否有一种有效的算法可以让我生成所有的排列而不必事后去除循环旋转？
注意：这不是使用Python,而是使用C语言.
解决方法
考虑测试您输出的每个排列,寻找比您所获得的更早“词法”的循环旋转.如果有,请不要返回 – 它将在其他地方枚举.
选择“唯一”第一个元素(如果存在)可帮助您进行优化.你知道如果你修复了第一个元素,并且它是唯一的,那么你就不可能通过旋转重复它.另一方面,如果没有这样的独特元素,只需选择最少的元素.这样,您只需要检查具有第一个元素的循环旋转. (例如,当你生成[1,1] – 你只需要检查[1,而不是[2,1]或[2,2] ]).
好吧,伪代码……显然是O(n！),我确信没有更聪明的方法,因为“所有符号不同”的情况显然必须返回(n-1)！元素.
// generate all permutations with count[0] 0's,count[1] 1's...
def permutations(count[])
if(count[] all zero)
return just the empty permutation;
else
perms = [];
for all i with count[i] not zero
r = permutations(copy of count[] with element i decreased);
perms += i prefixed on every element of r
return perms;
// generate all noncyclic permutations with count[0] 0's,count[1] 1's...
def noncyclic(count[])
choose f to be the index with smallest count[f];
perms = permutations(copy of count[] with element f decreased);
if (count[f] is 1)
return perms;
else
noncyclic = [];
for each perm in perms
val = perm as a value in base(count.length);
for each occurence of f in perm
test = perm rotated so that f is first
tval = test as a value in base(count.length);
if (tval < val) continue to next perm;
if not skipped add perm to noncyclic;
return noncyclic;
// return all noncyclic perms of the given symbols
def main(symbols[])
dictionary = array of all distinct items in symbols;
count = array of counts,count[i] = count of dictionary[i] in symbols
nc = noncyclic(count);
return (elements of nc translated back to symbols with the dictionary)
