Let $S_n$ be the symmetric group of $n$ letters, generated by elements $s_i$ for $ 1 \leq i \leq n -1$ with relations $s_is_{i+1}s_i = s_{i+1}s_is_{i+1} $ and $s_i,s_j$ commute if $|i-j| > 1$.
I would like to have an algorithm to get a list $w_1, \dots, w_{n!}$ which enumerates $S_n$ so that each $w_k$ can be expressed as a product in $s_1, \dots, s_{n-1}$.
For example for $S_3$ such a list is given by $1, s_1, s_2, s_1s_2, s_2s_1, s_1s_2s_1$. A list for $S_4$ or $S_5$ would be already nice.
Best Answer
For any $1\le i\le j\le n$, let $$ t^j_i=s_{j-1}s_{j-2}\cdots s_i, $$ with the convention that $t^i_i=1$. Any permutation in $S_n$ can be represented uniquely in the form $$ t^1_{a(1)}t^2_{a(2)}\dots t^n_{a(n)} $$ where $a(1),a(2),\dots,a(n)$ is a list of integers satisfying $1\le a(i)\le i$. Unpacking each $t^j_i$, you get an expression for each element of $S_n$ using the letters $s_i$.
The interpretation is that $t_{i}^j$ is a permutation which moves the item at slot $i$ to slot $j$, without disturbing any of the items above slot $j$.