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.
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$.
If you have the list of words (representing functions) for the $n$ group,
$$\quad w_1, w_2, \dots, w_{n!}$$
you can mechanically generate the words for the $n+1$ group using two facts:
$\quad \text{Every (new) permutation has the form } w \circ \tau \text{ for a transposition } \tau = (k \; \; n+1)$
$\quad \text{Every transposition can be written as a product of adjacent transpositions}$
We will use this theory to get the words for $S_4$.
To organize the work, we created a google sheet; here are the $24$ elements in $S_4$ ($s_0$ is the identity):
We did not work on representing these words with the shortest length. For example, the word in cell $\text{C7}$ can obviously be reduced in length.
I am not aware of the theory that would give us an algorithm to do this.
