Transpositions Back to 1234
The string 1234 is shuffled into one of its 24 permutations uniformly at random, and you are told the result is not 1234. You then sort it back using transpositions, swapping any two positions (not only adjacent ones), taking as few swaps as possible. For example 3241 needs two: 3241 to 1243 to 1234.
The minimum number of swaps for a permutation of items is minus its number of cycles. Grouping the 23 non-identity permutations by cycle structure:
| Cycle structure | How many | Cycles | Minimum swaps |
|---|---|---|---|
| one 2-cycle, two fixed points | 6 | 3 | 1 |
| one 3-cycle, one fixed point | 8 | 2 | 2 |
| two 2-cycles | 3 | 2 | 2 |
| one 4-cycle | 6 | 1 | 3 |
What is the expected number of swaps?
Sign in to answer questions and track your progress
Sign In