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

Question

因此，我需要一种算法来生成不包括循环旋转的数字列表的所有排列（例如 [1,2,3] == [2,3,1] == [3,1,2]）。

当序列中至少有 1 个唯一数字时，它相当简单，取出该唯一数字，生成剩余数字的所有排列（但对“标准”排列算法进行少量修改）并将唯一数字添加到前面。

为了生成排列，我发现有必要将排列代码更改为：

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,...,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 放回到排列中（类似于将 4 放在上面示例中的开头）。

这实际上只是查找所有 Lyndon 单词 来生成 项链

Answer 2

考虑测试您输出的每个排列，寻找“词汇上”早于您所获得的循环旋转。如果有，不要返回它 - 它会在其他地方被枚举。

选择“唯一”的第一个元素（如果存在）可以帮助您进行优化。您知道，如果您修复了第一个元素，并且它是唯一的，那么您不可能通过旋转来复制它。另一方面，如果没有这样的独特元素，则只需选择出现次数最少的元素即可。这样您只需要检查具有第一个元素的循环旋转。 （例如，当您生成 [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 3

该解决方案将涉及一些 itertools.permutations 用法，set()，和一些好的老式的设置差异。请记住，查找排列的运行时间仍然是 O(n!)。我的解决方案也不会内嵌执行此操作，但可能有一个更优雅的解决方案，允许您这样做（并且不涉及itertools.permutations）。为此，这是完成任务的直接方法。

步骤 1：使用给定的第一个元素生成循环的算法。对于列表 [1, 1, 2, 2]，这将为我们提供 [1, 1, 2, 2], [1, 2, 2, 1], [2, 1, 1, 2], [2, 2, 1, 1]。

def rotations(li):
    count = 0
    while count < len(li):
        yield tuple(li)
        li = li[1:] + [li[0]]
        count += 1

第 2 步：导入 itertools.permutations 以首先给出排列，然后将其结果设置到 set 中。

from itertools import permutations
perm = set(permutations([1, 1, 2, 2]))

第三步：使用生成器给我们自己的集合，以及循环（我们想要摆脱的东西）。

cycles = set(((i for i in rotations([1, 1, 2, 2]))))

步骤 4：对每个应用设置差值并删除循环。

perm = perm.difference(cycles)

希望这会对您有所帮助。我愿意接受建议和/或更正。

Answer 4

首先，我将展示我们将使用的容器和算法：

#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
#include <iterator>

using std::vector;
using std::set;
using std::sort;
using std::next_permutation;
using std::copy;
using std::ostream_iterator;
using std::cout;

接下来是我们的向量，它将代表排列：

typedef vector<unsigned int> Permutation;

我们需要一个比较对象检查排列是否是旋转：

struct CompareCyclicPermutationsEqual
{
    bool operator()(const Permutation& lhs, const Permutation& rhs);
};

以及 typedef 一个使用循环比较对象的 set：

typedef set<Permutation, CompareCyclicPermutationsEqual> Permutations;

然后主要功能非常简单：

int main()
{
    Permutation permutation = {1, 2, 1, 2};
    sort(permutation.begin(). permutation.end());

    Permutations permutations;

    do {
        permutations.insert(permutation);
    } while(next_permutation(numbers.begin(), numbers.end()))


    copy(permutations.begin(), permutations.end(),
         ostream_iterator<Permutation>(cout, "\n");

    return 0;
}

输出：

1, 1, 2, 2,
1, 2, 1, 2,

我还没有实现 <代码>CompareCyclicPermutationsEqual 然而。此外，您还需要实现 ostream&运算符<<(ostream&os, const Permutation& permutation)。