Question

So I think it's possible to create an infinite sequence of transpositions T = { ti, i ≥ 2 } satisfying ∀ i ∈ [2,n!]

• ∃ a,b ∈ [1,n] s.t. t_i = (a b)
• n!|(j - i) ⇒ tj = ti

such that if you consider the sequence of permutations P_n = { p_i,n, i ∈ [1,n!] } defined by

• p_1,n is the identity permutation
• p_i+1,n = p_i,n t_i+1

that P_n contains every permutation of n elements exactly once.

---

For example, if T starts with

{ (1 2), (1 3), (1 2), (1 3), (1 2), (1 4),
  (1 2), (1 3), (1 2), (1 3), (1 2), (2 4),
  (1 2), (1 3), (1 2), (1 3), (1 2), (3 4),
  (1 2), (1 3), (1 2), (1 3), (1 2), ....

then P₄ is given by

{ (1 2 3 4), (2 1 3 4), (3 1 2 4), (1 3 2 4), (2 3 1 4), (3 2 1 4),
  (4 2 1 3), (2 4 1 3), (1 4 2 3), (4 1 2 3), (2 1 4 3), (1 2 4 3),
  (1 3 4 2), (3 1 4 2), (4 1 3 2), (1 4 3 2), (3 4 1 2), (4 3 1 2),
  (4 3 2 1), (3 4 2 1), (2 4 3 1), (4 2 3 1), (3 2 4 1), (2 3 4 1) }

and P₄ contains every permutation of 4 elements exactly once.

---

What I'd like to find is a constructive proof for the existence of T. I'm sure I'm retreading old ground here, I just don't seem to be searching for the right terms to turn up what I'm looking for.

Answer 1

See for instance http://en.wikipedia.org/wiki/Steinhaus-Johnson-Trotter_algorithm.