# “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?

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.

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.

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:

• Knuth is using a very restricted set of transpositions, only those of the form $(i\ j)$ with $j=i+1$; this shows that in fact one can do even better than OP is looking for in the permutation case, but it also means that there may still be a Hamiltonian path of OP's form even through multisets (for instance, $2112$ and $2211$ would be adjacent in OP's graph but not in the given one.) – Steven Stadnicki Aug 29 '17 at 18:55
• "plain changes" must be a reference to the art of English change ringing. en.wikipedia.org/wiki/Change_ringing – Noam D. Elkies Aug 30 '17 at 0:00
• @Noam, yes, the bell ringing at Cambridge is mentioned on that page of Knuth's fascicle, among other things. – J. M. isn't a mathematician Aug 30 '17 at 0:12