3
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ @D.W. Took a pass at this, let me know if you still have concerns. $\endgroup$ Dec 9, 2021 at 18:30

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Interesting, thank you! The idea to derive a minimal labeling from a BFS of the Cayley graph is great. Now I'm curious if you know any efficient way to generate the Cayley graph from a set of generators :) One obvious brute force way would be to simply enumerate all products as: $a, b, aa, ab, ba, bb, aaa, aab, .. $ etc until you reach $N!$ distinct elements. But I think this would involve some unnecessary computations to collapse multiple representations of the same element like (e.g. bb = aaaa). $\endgroup$ Dec 9, 2021 at 21:25
  • $\begingroup$ I seem to have found a comment in this lecture (top of page 7) that might imply it's a difficult problem in general, but would love any pointers to something more specific: > This is the computationally “difficult” part of this algorithm. In > general, finding the Cayley graph, or even more simply determining whether two > arbitrary words in a presented graph are equal, is an undecidable problem: it is > provable that no algorithm exists that will always solve this problem $\endgroup$ Dec 9, 2021 at 22:09
  • 1
    $\begingroup$ @JaredStewart, yes, generate the Cayley graph by doing BFS starting from a fixed node (the identity permutation). Note that given any node you can easily find the edges out of it, and thus you have everything you need to build up the graph on the fly, using BFS to do so. It is easy to do; the only problem is that the graph has $n!$ nodes so takes $n!$ space to represent and $n! \times |G|$ steps of computation to build. $\endgroup$
    – D.W.
    Dec 9, 2021 at 22:15
  • $\begingroup$ Let me try to show you what I mean about avoiding unnecessary complications. Looking at the Cayley graph of $S_4$ You always know that if the previous arrow to a vertex was green, you won't reach a new element from the edge produced by applying the green element again to that vertex (this is basically the relation $b^2=1$). Is there any general way to avoid unnecessary edges based on the relations of the elements in the generating set? $\endgroup$ Dec 9, 2021 at 22:24
  • 1
    $\begingroup$ @JaredStewart, that last question sounds like a question to pose on Math.SE. $\endgroup$
    – D.W.
    Dec 9, 2021 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.