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

it's slightly easier to go for this bottom up:

if A only contains 1 element, P(A) also contains one permutation. it's easy to see the same works if A only contains 2 elements.

Now, let's assume you already have all P(A) for A with n elements, and you add one element. it can go in any of n spots in any of the permutations in P(A).

I think this idea translates pretty directly to a recursive algorithm in your language of choice, and hope my explanation was clear enough.

EDIT: I know i kind of ignored the fact that A may contain duplicate elements, but still thinking about that part :)

just as a though - if you sorted A before starting the permutation algorithm, I think this might eliminate duplicates. (still thinking about that too)

Answer 2

Sawada's algorithm

Answer 3

For an intuitive understanding of the problem I think we can employ this metaphor. Visualize a clock on the wall but instead of having 12 positions on the face it has n where n is the number of elements in your set.

Then the each equivalence class is just an assignment of an element of A to a position on the clock face.

Once assigned another permutation from the same equivalence class can be generated by simply rotating the clock on the wall.

To generate another unrelated permutation of A you need to have an element skip over at least one other element.

Now the algorithm as I see it would be to start with an assignment for example say we had four elements in A = {a, b, c, d} and we assigned them to the 12, 3, 6 and 9 positions respectively for visual clarity. Then our first operation would be to swap a and b. then a and c, then a and d, then we would go to b and swap it with the element in the 3 position which now is c.

Doing this until we reached d would generate a representative from all the equivalence classes.

This doesn't take care of duplicates but it should be far more efficient than generating all permutations of A.

Answer 4

The thought that springs to my mind is that for any set that has at least one element that only appears once then you can put that element in the first position of your list for all answers and then generate all permutations of the rest of the numbers. This is a pretty trivial solution since the fact your first element is unique ensures that there are no equivalents by cycle shifting the elements. Clearly then all the solutions you generate must be unique.

The obvious problem is that if you have no elements that are singles then this breaks down entirely. The main reason that I put this in is becasue there are several other solutions dealing with no duplicates and I think this one is more effective than them (solves more cases) so is worthy of mention. Its also pretty simple in terms of understanding how it works and implementing it. I just hope my reasoning is sound. ;-)

Edit for further thoughts:

It occurs to me that this principle can be extended to the situation where you have duplicates to a certain extent.

If you take one element (that we assume now is repeated) you can look at just its permutations and which ones would allow for cycle shift repetition, as before assumign that you can "lock" one in place without loss of generality. eg if you have a total of 6 elements and A appears twice in this set then you can have:

AAXXXX, AXAXXX, AXXAXX, AXXXAX, AXXXXA

The last of these is the same as the first (within cyclic shift) so can be ignored, ditto the second and fourth. The third (AXXAXX) can be cycled by three to get back to itself so has the potential for cycles. The first two can never give rise to cycles no matter how many times you cycle them so however you distribute the remaining elements you need only ensure that they are unique distributions and you are guaranteed to get unique by cycle results.

For the third pattern that can cycle (AXXAXX) you would need to look at element B and repeat the process for those. This time unfortuantely you would be unable to use the trick of locking the first value to save time.

I'm not 100% sure how you would go about making this into a fully working program but its some thougths on how to avoid having to brute force.