Iteratively enumerating all permutations of $N$ objects using a generating set

Question

The group theory of $S_n$ shows that all permutations of $n$ objects can be generated from the $n$-cycle $a:=(1 2 3 .. n)$ and the transposition $b:=(1 2)$. (See Theorem 2.5 at https://kconrad.math.uconn.edu/blurbs/grouptheory/genset.pdf)

One can use this fact to label and enumerate permutations. For example, this shows such an enumeration for $S_3$ where the left hand side shows the action of the given element on $[0 1 2 3]$ and the right hand side shows a "labeling" representation in terms of $a$ and $b$:

0 1 2 3  () 
1 2 3 0  (a) 
2 3 0 1  (aa) 
3 0 1 2  (aaa) 
0 3 1 2  (aaab) 
3 1 2 0  (aaaba) 
1 2 0 3  (aaabaa) 
2 0 3 1  (aaabaaa) 
0 2 3 1  (aaabaaab) 
2 3 1 0  (aaabaaaba) 
3 1 0 2  (aaabaaabaa) 
1 0 2 3  (aaabaaabaaa) 
1 3 0 2  (aaabaaabaaab) 
3 0 2 1  (aaabaaabaaaba) 
0 2 1 3  (aaabaaabaaabaa) 
2 1 3 0  (aaabaaabaaabaaa) 
2 0 1 3  (aaabaaabaaabaaab) 
0 1 3 2  (aaabaaabaaabaaaba) 
1 3 2 0  (aaabaaabaaabaaabaa) 
3 2 0 1  (aaabaaabaaabaaabaaa) 
1 0 3 2  (aaabaaabaaabaaabaab) 
0 3 2 1  (aaabaaabaaabaaabaaba) 
3 2 1 0  (aaabaaabaaabaaabaabaa) 
2 1 0 3  (aaabaaabaaabaaabaabaaa) 

Making this more precise, given any element $\sigma \in S_n$ and a generating set G we can find some positive integer $k$ and $d_i \in G$ for $ 1 \leq i \leq k$ such that $\sigma = \sum_{i=1}^{k} d_i$.

Let's say that a "labeling" is a map that sends every element $\sigma$ of $S_n$ to a specific choice of representation $d_{\sigma, 1}, ..., d_{\sigma, k_\sigma}$.

This observation leads to some interesting questions:

1. Is there a straightforward way to produce a labeling for $S_n$ given a generating set $G$?

2. Even better, can you produce a minimal labeling in the sense that no element could be represented by a shorter product of elements from the generating set?

3. Is there a correspondence between this method of generating permutations and the classical solutions like backtracking, "plain changes", or Heap's method, perhaps given some other set of generating elements rather than this specific choice of $a$ and $b$? (See https://www.cs.princeton.edu/~rs/talks/perms.pdf) That is, does there exist a choice of generating set G and labeling L that would enumerate the elements in the same order as the other methods when the elements are sorted by label lexicographically?

Thanks in advance!

Answer 1

My suggestion would be to build up the Cayley graph for $S_n$ with generating set $G$ iteratively, using breadth-first search to traverse the graph. This will give you a labelling for every element of $S_n$, and moreover, because breadth-first search finds the shortest paths, it will also give you a minimal labelling.

I don't know whether there is any relationship to those other methods of enumerating permutations.