Computing short generator sequences

The diameter of a group is the length of the longest product of generators required to reach a group element. We show that the diameter of a permutation group of degree n generated by cycles of bounded degree is O(n 2). This bound is the best possible. Additionally, such short products can be found in polynomial time. The techniques presented here may be applied to many permutation-group puzzles such as Alexander's Star, the Hungarian Rings, Rubik's Cube, and some of their generalizations.

Authors

• James R. Driscoll
• Merrick L. Furst

Keywords

No keywords are indexed for this paper.