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?



"Gray code" of all permutations
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](http://www.coga.tu-berlin.de/fileadmin/i26/coga/kompelmakherLiskovets.pdf): 



> 
> 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)](https://doi.org/10.1137/S0036144595295272):



> 
> 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*](https://books.google.com/books?id=iM0fco-_Ri8C).


