生成不包括循环转动

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 ]）。

---

OK，伪...显然为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

该解决方案将涉及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])) 

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

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

第4步：对每个应用设置差异，并删除周期。

perm = perm.difference(cycles) 

希望这会帮助你。我愿意接受建议和/或更正。

Answer 3

对于所有数字都不同的置换情况，这很简单。假设这些数字是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 words的情况下产生necklaces

Answer 4

首先我会告诉容器和算法，我们会using：

#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; 

接下来我们vector这将代表Permutation：

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& operator<<(ostream& os, const Permutation& permutation)。