是否有一个算法来生成一个多重的所有独特的环形排列？ [英] Is there an algorithm to generate all unique circular permutations of a multiset?

问题描述

我做一些热心的编程时遇到了这个问题。这个问题可以pssed EX $ P $如下：

I encountered this problem when doing some enthusiastic programming. The problem can be expressed as follows:

对于多集A，令P（A）表示   集A的所有可能的排列   P（A）自然分成   不相交的子集是等价   类，具有同值关系   是可以通过循环的变化有关。枚举所有   这些等价类通过生成   正是从他们每个人的一员。

For a multiset A, let P(A) denote the set of all possible permutations of A. P(A) is naturally divided into disjoint subsets that are equivalence classes, with the equivalence relation being "can be related by circular shifts." Enumerate all these equivalence classes by generating exactly one member from each of them.

例如，考虑多集{0，1，1，2}。的置换0112和1201是独特的排列，但是后者可以通过发现圆形移前，反之亦然。所需的算法不应该同时产生。

For example, consider the multiset {0, 1, 1, 2}. The permutations "0112" and "1201" are unique permutations, but the latter can be found by circular-shifting the former and vice versa. The desired algorithm should not generate both.

当然，蛮力方法是可行的：只是产生排列 - 不管圆形重复 - 使用任何的多集排列算法，并放弃与previous结果对比发现重复。然而，这往往是低效率的在实践中。所需的算法应该需要最少的，如果不是零记账。

Of course a brute-force approach is possible: just generate permutations -- regardless of circular duplication -- using any of the multiset permutation algorithms, and discard duplications found by comparison with previous results. However, this tends to be inefficient in practice. The desired algorithm should require minimal, if not zero bookkeeping.

任何见解了这个问题深感AP preciated。

Any insights into this problem is deeply appreciated.

推荐答案

<一个href="http://byorgey.word$p$pss.com/2010/03/12/math-combinatorics-multiset-and-sawadas-algorithm/">Sawada's算法

这篇关于是否有一个算法来生成一个多重的所有独特的环形排列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！