Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  Lee Mosher Jun 16 '12 at 19:05
1  
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. –  Ng Yong Hao Jun 16 '12 at 19:18
2  
Are you asking for a Hamiltonian path in the Cayley graph of S_n with these two generators? –  John Wiltshire-Gordon Jun 16 '12 at 19:21
1  
2  
(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. –  Brendan McKay Jun 17 '12 at 3:02

1 Answer 1

up vote 14 down vote accepted

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.

share|improve this answer
    
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. –  Ng Yong Hao Jun 16 '12 at 20:27
    
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. –  Ng Yong Hao Jun 16 '12 at 20:51
    
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. –  Benjamin Steinberg Jun 17 '12 at 3:04
    
@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? –  Ng Yong Hao Jun 17 '12 at 14:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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