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$ – Chad Brewbaker Jan 6 '14 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.