# List of symmetric group elements from the usual presentation

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.