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.

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.

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.

Any insights into this problem is deeply appreciated.

Answer 1

Sawada's algorithm