12
$\begingroup$

It is well known that all symmetric group can be generated using two generators

The two generators are:
1) $(1,2)$
2) $(1,2,3,\dots ,n)$

Question: Is there a deterministic algorithm to generate all permutations without repetition using only these two generators?
(Bonus 1: The algorithm generates the permutations in a cycle. Bonus 2: Not requiring the inverse of generator 2)
Edit: As point out by John, this is equivalent to a Hamiltonian path in the Cayley graph of $S_n$ with these two generators.

It is easy to generate all of them without repetition using $n-1$ generators, by the Steinhaus-Johnson-Trotter algorithm.
It is easy to generate all of them, with repetition, using two generators.
However I was unable to find a way to generate all without repetition and using only two generators.

As this approach seems natural, I suspect someone should have worked on it but I was unable to find any references online.

Does anyone knows the status of this problem?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Answer: Yes. In fact, there is an algorithm that works for any finite group and any generating set. Using lexicographical order of the words, go through them one at a time, and compute the product. If the product has not yet been encountered, add it to the list of elements of the group. If the product has already been encountered, move on to the next word. Stop when you have all elements of the group. This also satisfies Bonus 2. If that is not what you want, you will have to be more precise about what kind of algorithm you want. For instance, I do not know what you mean by Bonus 1. $\endgroup$
    – Lee Mosher
    Commented Jun 16, 2012 at 19:05
  • 1
    $\begingroup$ Thanks for the fast response. I am thinking of the following: start with the identity $(1,2,\dots,n)$. Apply either generator 1 or generator 2 to get a new element. Proceed until all elements are covered. Bonus 1 means that after getting the last element, applying either generator 1 or 2 gets you the identity. I just added a "deterministic" requirement for the algorithm and by this I mean the sequences of generators to be used is known before hand. $\endgroup$
    – Ng Yong Hao
    Commented Jun 16, 2012 at 19:18
  • 4
    $\begingroup$ Are you asking for a Hamiltonian path in the Cayley graph of S_n with these two generators? $\endgroup$
    – John Wiltshire-Gordon
    Commented Jun 16, 2012 at 19:21
  • 1
    $\begingroup$ amazon.com/The-Computer-Programming-Volume-Fascicle/dp/… $\endgroup$
    – Steve Huntsman
    Commented Jun 17, 2012 at 0:19
  • 5
    $\begingroup$ (I'm not making this an answer because I don't have the references I need.) The strongest form of your question is where you need a hamiltonian cycle (not just path) in the Cayley digraph (so the inverse of generator 2 is not used). This has been proved impossible for even $n$. For odd $n$ I did it by computer up to $n=11$ (that's a digraph of 39,916,800 vertices) but as far as I know the question remains open. $\endgroup$
    – Brendan McKay
    Commented Jun 17, 2012 at 3:02

2 Answers 2

Reset to default
21
$\begingroup$

Your question is a special case of the Lovász conjecture, which says that all Cayley graphs are Hamiltonian. According to Igor Pak (Hamiltonian Paths in Cayley Graphs) there is an explicit Hamiltonian Cycle on your two generators which requires only linear space to compute. The construction is purported to reside in this paper (which I cannot access):

R. C. Compton, S. G. Williamson, Doubly adjacent Gray codes for the symmetric group, Linear and Multilinear Algebra 35 (1993), 237–293.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is exactly what I was looking for! Thank you. I wanted to try this for "recreation" but I was worried that it may turn out to be a very difficult problem. I can see the first part of the paper which quotes: "The existence of such a code seems to be a very nontrivial problem" so the authors seem to agree. Nevertheless it is still nice to know that such a nice result exists. $\endgroup$
    – Ng Yong Hao
    Commented Jun 16, 2012 at 20:27
  • $\begingroup$ I would like to also add that by searching for related papers, I found "A Survery of Combinatorial Gray Codes", where on page 13 the authors commented that the algorithm by R.C. Compton and S.G. Williamson is rather complex. So unfortunately it appears that this cannot be used for practical purposes. $\endgroup$
    – Ng Yong Hao
    Commented Jun 16, 2012 at 20:51
  • $\begingroup$ Linear space is not as nice as it sounds. For instance in n cells with a 2 letter alphabet you can write successively all 2^n words. $\endgroup$
    – Benjamin Steinberg
    Commented Jun 17, 2012 at 3:04
  • $\begingroup$ @Benjamin: My apologies for my ignorance, but I am not sure if I understood what you wrote. Please correct me if I am wrong: Do you mean that each of the $n$ cell holds 1 alphabet and hence it is possible that the generation requires enumeration of up to $2^n$ words? $\endgroup$
    – Ng Yong Hao
    Commented Jun 17, 2012 at 14:34
3
$\begingroup$

There has been a recent paper by Sawada and Williams where the problem is solved for the harder variant where you always shift in the same direction, i.e., you never require the inverse of generator 2 (Bonus 2 problem). The paper is available here:
https://epubs.siam.org/doi/abs/10.1137/1.9781611975031.37

A demonstration of that algorithm can be run on the Combinatorial Object Server website:
http://page.math.tu-berlin.de/~muetze/cos/
Go to "Permutations", then select "Prefix swaps and rotations (Sawada-Williams)".

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .