Hamiltonian path in $S_n$? Say $S_n$ is the symmetric group. Define a graph $G$ by $G=(S_n,E)$, where there is an edge from $\sigma_1$ to $\sigma_2$ if and only if $\sigma_2=t\sigma_1$ for some transposition $t$.
Is there a Hamiltonian path in $G$? If yes, is there a convenient way to define such a path?
No work so far - sue me. Context: For no practical reason, thinking about an elegant implementation of the formula $$\det(A)=\sum_{\sigma\in S_n}\text{sgn}(\sigma)\prod_{j=1}^n a_{j,\sigma(j)}.$$
 A: Yes, such Hamiltonian path exists and it can obtained just by swapping adjacent elements between two successive permutations. The procedure to generate it is called the Steinhaus–Johnson–Trotter algorithm.
For example, for $S_4$, it gives the following Hamiltonian path (actually a cycle) through the $4!=24$ permutations:
$$123\color{blue}{4}\to 12\color{blue}{4}3\to  1\color{blue}{4}23\to  \color{blue}{4}1\color{red}{23}\to\\
\color{blue}{4}132\to 1\color{blue}{4}32
\to 13\color{blue}{4}2\to  \color{red}{13}2\color{blue}{4}\to\\  
312\color{blue}{4} \to 31\color{blue}{4}2\to  3\color{blue}{4}12\to  \color{blue}{4}3\color{red}{12} \to\\
 \color{blue}{4}321\to  3\color{blue}{4}21\to  32\color{blue}{4}1 \to \color{red}{32}1\color{blue}{4}\to\\  
231\color{blue}{4}\to  23\color{blue}{4}1\to 2\color{blue}{4}31\to \color{blue}{4}2\color{red}{31}\to\\  \color{blue}{4}213\to  2\color{blue}{4}13 \to 21\color{blue}{4}3\to  \color{red}{21}3\color{blue}{4}\to$$
A: Yes.
For $S_1$ and $S_2$, this is trivial.
For $S_n$ with $n\ge 2$ apply recursion: 
Starting with the identity, a Hamiltonian path for $S_{n-1}$ allows you to walk through all $(n-1)!$ permutations of $\{1,\ldots,n\}$ that map $n\mapsto n$.
More generally, if you start with any $\sigma\in S_n$, this allows you to walk through all $(n-1)!$ permutations of $\{1,\ldots,n\}$ that map $n\mapsto \sigma(n)$.
To get all $n!$ elements of $S_n$, start with all permutations mapping $n\mapsto n$. Then apply $(n\,n-1)$ and walk through all permutations mapping $n\mapsto n-1$. Then apply $(n-1\,n-2)$ and walk through all permutations mapping $n\mapsto n-2$. Then ...

Regarding your goal with the determinant: Note that this method will cost you $O(n!)$ operations, whereas the Gauss algorithm uses only $O(n^3)$.
