[It is well known that all symmetric group can be generated using two generators](http://www.wiki.canisiusmath.net/index.php?title=Well-Known_Generators_of_the_Symmetric_Group)


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](http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_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?



Generating All Permutations Without Repetition Using Two Generators
Your question is a special case of the [Lovász conjecture](http://en.wikipedia.org/wiki/Lovasz_conjecture), which says that all Cayley graphs are Hamiltonian. According to Igor Pak ([Hamiltonian Paths in Cayley Graphs](http://www.math.ucla.edu/~pak/papers/hamcayley9.pdf)) 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.


