# Generating All Permutations Without Repetition Using Two Generators

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?

-
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
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
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
(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

@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