Here is the problem as posed by Jerrum:

"The computational complexity of the following problem is investigated: Given a permutation group specified as a set of generators, and a single target permutation which is a member of the group, what is the shortest expression for the target permutation in terms of the generators?"

Jerrum, Mark R. "The complexity of finding minimum-length generator sequences." Theoretical Computer Science 36 (1985): 265-289.

What is the current state of the art algorithm for finding min-length generator sequences over small ( n<13 ) permutations?

The simple approach seems to be caching prefixes and growing them when a length $i+1$ word (composed into a permutation) is not contained in any of the length $1..i$ words. You either reach the target permutation, or at some length your words no longer compose into new permutations so you know the target is unreachable.

  • $\begingroup$ Also, the weighted version of this problem where each generator has an associated cost would be nice for the particular application I have in mind. $\endgroup$ Jan 6, 2014 at 23:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.