0

Suppose you have a sequence, \$S\$, of \$n\$ items and you want to enumerate all possible permutations of those items.

Consider the transformation $$ S^{\prime} = ( S_{a_1}, S_{a_2} ... S_{a_n} ) $$

Is there a transformation (specifically, a permutation) such that if it is repeated \$n!\$ times, all permutations of \$S\$ will be reached exactly once? (not counting the starting sequence)

For \$n = 2\$, this is trivial. Simply swapping the two elements is guaranteed to produce both permutations when repeated twice.

This is not possible for \$n = 3\$.

  • \$ ( 3, 1, 2 ) \$ and \$ ( 2, 3, 1 ) \$ will merely rotate the sequence, covering exactly 3 out of the 6 possible permutations.
  • No other permutations of three items are derangements, therefore it is not possible to reach all permutations, as some elements are left in place.

It doesn't work for \$n = 4\$

  • Rotations \$ (2, 3, 4, 1) \$ and \$ (4, 1, 2, 3) \$ will not work for the same reason as the \$n = 3\$ case
  • \$ (3, 4, 1, 2) \$ is the same as 2 rotations
  • The reverse permutation \$ (4, 3, 2, 1) \$ does not work, as it only reaches two permutations
  • \$ (2, 4, 1, 3) \$ has a period of 4: ABCD -> BDAC -> DCBA -> CADB -> ABCD
    • Its reverse, \$ (3, 1, 4, 2) \$, would have the same effect
  • \$ (2, 1, 4, 3) \$ only exchanges adjacent pairs and can't possibly work
  • \$ (3, 4, 2, 1) \$ has a period of 4: ABCD -> CDBA -> BADC -> DCAB -> ABCD
    • \$ (4, 3, 1, 2) \$ behaves similarly
  • No other transformations are derangements

Is this even possible for any \$n > 2\$?

Novice
  • 1,127
Beefster
  • 181

1 Answers1

8

No if $n>2$ because the symmetric group $S_n$ is not cyclic.

I gave a definition in the comment. But one could argue without using groups. If you can get all permutations by repeating one permutation $p$ then for any two permutations $c,d$ you would have $cd=dc$ because $c=pp...p$ ($k$ times) and $d=pp...p$ ($m$ times), $cd=dc=pp...p$ ($k+m$ times). This is not the case: take $c=(1,2), d=(2,3)$ (assuming n>2).

markvs
  • 19,653