Algorithm for decomposing permutations - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T09:22:59Z http://mathoverflow.net/feeds/question/11758 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11758/algorithm-for-decomposing-permutations Algorithm for decomposing permutations Charles Siegel 2010-01-14T15:17:42Z 2010-01-14T21:56:26Z <p>Is there an algorithm for solving the following problem: let \$g_1,\ldots,g_n\$ be permutations in some (large) symmetric group, and \$g\$ be a permutation that is known to be in the subgroup generated by \$g_1,\ldots,g_n\$, can we write \$g\$ explicitly as a product of the \$g_i\$'s?</p> <p>My motivation is that I'm TAing an intro abstract algebra course, and would like to use the Rubik's cube to motivate a lot of things for my students, and would, in particular, like to show them an algorithm to solve it using group theory. (That is, I can write down what permutation of the cubes I have, and want to decompose it into basic rotations, which I then invert and do in the opposite order to get back to the solved state.) Though I'm interested in the more general case, not just for the Rubik(n) groups, if a solution works out.</p> <p>Note: I don't really know what keywords to use for solving this problem, if someone can point me to the right search terms to google to get the results I'm looking for, I'll gladly close this.</p> http://mathoverflow.net/questions/11758/algorithm-for-decomposing-permutations/11760#11760 Answer by Mitch for Algorithm for decomposing permutations Mitch 2010-01-14T15:35:56Z 2010-01-14T15:42:14Z <p>See this paper:</p> <p><a href="http://www.dartmouth.edu/~rah/games-with-algorithms.pdf" rel="nofollow">http://www.dartmouth.edu/~rah/games-with-algorithms.pdf</a></p> <p>Page 22 contains a survey of the problem you're interested in. Apparently, there is a polynomial time algorithm to check if a solution exists (it will also return some implicitly represented solution), but finding the solution with the fewest number of moves is, not surprisingly, PSPACE-complete.</p> <p>The original reference is:</p> <p>Mark Jerrum: The Complexity of Finding Minimum-Length Generator Sequences. Theor. Comput. Sci. 36: 265-289 (1985)</p> http://mathoverflow.net/questions/11758/algorithm-for-decomposing-permutations/11783#11783 Answer by David Eppstein for Algorithm for decomposing permutations David Eppstein 2010-01-14T21:56:26Z 2010-01-14T21:56:26Z <p>Yes. The general rule of thumb is that groups described by permutations are computationally easy, groups described by generators and relations have computational problems that are generally undecidable, and matrix groups are somewhere in between.</p> <p>There's a whole book "Permutation group algorithms" by Seress, Cambridge University Press, 2003.</p> <p>The main technique for permutation groups is called the Schreierâ€“Sims algorithm; there's a survey <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.3009&amp;rep=rep1&amp;type=pdf" rel="nofollow">here</a>, for instance. The rough idea is to stabilize the permuted elements one at a time. As Mitch already said, though, this doesn't find the shortest word in the generators that produces any particular group element, which is a more difficult problem.</p>