Is there an algorithm to generate all unique circular permutations of a multiset?

Question

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

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"是唯一的排列,但后者可以通过对前者进行循环移位来找到,反之亦然.所需的算法不应生成两者.

当然,蛮力方法是可能的:只需生成排列 - 无论循环重复 - 使用任何多重排列算法,并丢弃与先前结果相比较的重复.然而,这在实践中往往效率低下.如果不是零记账,所需算法应该要求最少.

深刻理解对此问题的任何见解.

Answer 1

泽田的算法