"Gray code" of all permutations Informally asking, can we step through all permutations of the set $\{1,\ldots,n\}$ by just using transpositions?
More formally: For any $n\in\mathbb{N}$ let $[n] = \{1,\ldots,n\}$ and let $S_n$ be the set of all bijections (permutations) $\pi:[n]\to [n]$. For any set $X$ let  $[X]^2 = \big\{\{x,y\}: x\neq y\in X\big\}$. We let $\pi,\psi\in S_n$ be connected by an edge if "they are one transposition away from each other", or more formally, set $$E_n = \big\{\{\pi,\psi\}\in [S_n]^2:\exists a<b\in[n]:\psi = (a\;\;b)\circ\pi\big\}.$$
For what $n\in\mathbb{N}$ does the graph $(S_n, E_n)$ allow for a Hamiltonian cycle? Or at least for a Hamiltonian path?
 A: In Knuth's second fascicle of volume 4 of The Art of Computer Programming, he gives "algorithm P" (or more colloquially, the method of plain changes) for generating the permutations of a sequence with distinct elements by repeatedly interchanging adjacent pairs.


Earlier in the book, however, Knuth gives a cold shower on the possibility of doing something similar for multisets with repeated elements. He gives the following example, which does not have a Hamiltonian path:

A: From V. L. Kompel'makher and V. A. Liskovets, "Sequential generation of arrangements by means of a basis of transpositions", Kibernetika 3, 17, May-June, 1975: 

It is well known ([1], p. 28) that all $n!$ arrangements of $n$ symbols can be ordered without repetition so that each can be obtained from the previous one by a single transposition. 

See also C. Savage, "A survey of combinatorial Gray codes", SIAM Rev., 39, 605 (1997):

Examples of combinatorial Gray codes include (1) listing all permutations of $1  \dots n$ so that consecutive permutations differ only by the swap of one pair of adjacent elements
  [Joh63, Tro62]

This is also addressed in Example 7.3.1 in Joyner's Adventures in Group Theory.
