If $n>0$ is an integer, let $[n]=\{1,\ldots,n\}$. Let $S\_n$ denote the set of all permutations (bijections) $\pi:[n]\to[n]$.


For which positive integers $n$ is there a bijection $\Phi:[n!]\to S\_n$ such that for all $x\in[n!-1]$ we have
$ (\Phi(x))(k) \neq (\Phi(x+1))(k) \text{ for all }k\in [n]$?




---


**Note.** This can be formulated in the language of Hamiltonian paths: Put a graph structure on $S\_n$ saying that $\pi\_1,\pi\_2\in S\_n$ form an edge if $\pi\_1(k)\neq \pi\_2(k)$ for all $k\in[n]$, and find a Hamiltonian path in this graph.



Arranging all permutations on $\{1,\ldots,n\}$ such that there are no common points
We are basically looking at the [Cayley graph](https://en.wikipedia.org/wiki/Cayley_graph) of $S\_n$ where the generating set is the set of all [derangements](https://en.wikipedia.org/wiki/Derangement). The question is whether this graph is Hamiltonian.


I will quote here a paper by Rasmussen and Savage, several further references on this problem can be found there


David J. Rasmussen, Carla D. Savage: *Hamilto-connected derangement graphs on $S\_n$*, Discrete Mathematics, Volume 133, Issues 1–3, Pages 217-223; [DOI: 0012-365X(94)90028-0](https://doi.org/10.1016/0012-365X(94)90028-0), [Zbl 0808.05069](https://zbmath.org/?q=an%3A0808.05069), [MR1298976](https://mathscinet.ams.org/mathscinet-getitem?mr=1298976)



> 
> **Abstract.** We consider the *derangements graph* in which the vertices are permutations of $\{1,\dots,n\}$. Two vertices are joined by an edge if the corresponding permutations differ in every position. The derangements graph is known to be hamiltonian and it follows from a recent result of Jung that every pair of vertices is joined by a Hamiltonian path. We use this result to settle an open question, by showing that it is possible, for any n and k satisfying $2\le k\le n$ and $k\ge3$, to generate permutations of $\{1,\dots,n\}$ so that successive permutations differ in $k$ consecutive positions. In fact, the associated $k$-consecutive derangements graph is also Hamilton-connected.
> 
> 
> 


