# Sequence of transpositions that generates the set of permutations

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. ti = (a b)
• n!|(j - i)tj = ti

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

• p1,n is the identity permutation
• pi+1,n = pi,n ti+1

that Pn 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 P4 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 P4 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.

-
@Richard Stanley: Thanks! The link you gave was broken, but it was enough for me to find Wikipedia's page on the Steinhaus–Johnson–Trotter algorithm. If you'd like to upgrade your comment to an answer, I'd be happy to accept it. – user1596 Mar 17 '12 at 22:43
O.k., I will upgrade my comment. I am glad it helped. – Richard Stanley Mar 17 '12 at 23:55