Is there a sequence of swaps that would generate all possible permutations? [closed]

Question

You are given a list of numbers 1, 2, ... ,n - is there a sequence of n!-1 swap operations that would generate all n! permutations of the list where swap (i, j) swaps elements at cell i and j? What about the general case when the input list is not sorted to start with and/or there are repetitions in the list?

Context: I am solving a problem where the "score" of an array is easy to calculate if you already know the score if 2 elements are swapped and I want to brute force (using C++ next_permutation()) all possible permutations.

Answer 1

Sure, and it was known to 17th century bell-ringers. So how's that for a bit of combinatorial history?

See the Steinhaus Johnson Trotter algorithm or consult your local change-ringing group.

---

I did a bit of research on the second part of your question, which is whether it is possible to do this with repeated elements. The answer, I believe, is "yes, but not so easily". Furthermore, it is not possible to permute a list with repeated elements with just adjacent swaps, as can be easily seen for the set {0, 0, 1, 1}. However, it is possible with just single swaps.

The basic approach is to use the basic change-ringing algorithm, but on groups of identical elements instead of on single elements. For a group of k identical elements, you need to be able an algorithm for combinations of the list 0^n-k1^k (where n is the total size of the base set). A number of such algorithms exist, but I can't find any which are really simple; the simplest one is (roughly speaking) to assign a direction to the overall group, and also a direction to each 1 (in a similar fashion to the Shimon Even algorithm). When moving the group left, the leftmost element sweeps back and forth; every time it changes direction, the next mobile element to the right steps one; etc. This eventually moves the entire group from the right-hand side of the list to the left-hand side, after which its overall direction is flipped and it proceeds back to the original configuration, now with the rightmost element leading the sweeps.

Since the number of direction reversals might be even in this case, the above algorithm might not trace out a permutation cycle, but I believe that it is possible to produce a cycle using a more sophisticate algorithm. In effect, you're looking for a hamiltonian cycle in the graph induced by possible single swaps from each permutation -- a variant of the permutehedron -- but, while hamiltonian cycles do exist, they are not so easy to find since the graphs are quite large.