Skip to main content
added 128 characters in body
Source Link
Ng Yong Hao
  • 360
  • 1
  • 4
  • 12

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?

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)

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?

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?

Source Link
Ng Yong Hao
  • 360
  • 1
  • 4
  • 12

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)

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?