生成除循环旋转之外的所有排列

Question

所以我需要一个算法来生成除循环旋转之外的数字列表的所有排列(例如[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,1,2,2]它将输出[1,1,2,2],[1,2,2,1]和[1,2] ,1,2]和前两个是循环旋转.

那么是否有一种有效的算法可以让我生成所有的排列而不必事后去除循环旋转？

如果不是,那么删除循环旋转的最有效方法是什么？

注意:这不是使用Python,而是使用C++.

Answer 1

考虑测试您输出的每个排列,寻找比您所获得的更早"词法"的循环旋转.如果有,请不要返回 - 它将在其他地方枚举.

选择"唯一"第一个元素(如果存在)可帮助您进行优化.你知道如果你修复了第一个元素,并且它是唯一的,那么你就不可能通过旋转重复它.另一方面,如果没有这样的独特元素,只需选择最少的元素.这样,您只需要检查具有第一个元素的循环旋转.(例如,当你生成[1,2,2,1] - 你只需要检查[1,1,2,2],而不是[2,2,1,1]或[2,1,1,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)

Answer 2

对于所有数字都不同的排列情况,这很简单.说数字是1,2,...,n,然后生成所有的排列1,2,...,n-1并坚持n在前面.这给出了全套模数循环旋转的所有排列.例如,n=4你可以这样做

4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

这确保了每个排列的一些循环旋转1,2,3,4在列表中恰好出现一次.

对于您想要多集的排列(允许重复输入)的一般情况,您可以使用类似的技巧.删除最大字母的所有实例n(类似于忽略4上例中的)并生成剩余多字节的所有排列.下一步是以n规范的方式将s 放回到排列中(类似于4在上面的例子中将其放在开头).

这实际上只是找到所有Lyndon单词来生成项链的情况