2
$\begingroup$

You're given $k$ permutations $a_1,\dots,a_k$. Consider closure of this set under the composition operation. What are most efficient and simple algorithms to calculate the size of this closure?

$\endgroup$
  • $\begingroup$ Don't think there are efficient algorithms for doing this in a classical setting $\endgroup$ – Samuel Schlesinger Nov 6 '17 at 14:32
  • $\begingroup$ I doubt that since there at least one such algorithm in Polynomial-time algorithms for permutation groups. What is asked here is maybe some general overview of existing algorithms and their key ideas. $\endgroup$ – Oleksandr Kulkov Nov 6 '17 at 18:26
  • 1
    $\begingroup$ If you already know of some algorithms for this problem, please edit your question to provide a summary of the algorithms/references you already know of. As our help center says, "Try to make your question interesting for others by providing some background knowledge. Remember, questions should be based on knowledge sharing". $\endgroup$ – D.W. Nov 7 '17 at 23:55
7
$\begingroup$

The most efficient (and also simplest) algorithms for this are based on the notion of a strong generating set, introduced by Sims. Strong generating sets can be computed efficiently using the Schreier-Sims algorithm. Essentially any introductory book that talks about computational group theory should have a decent introduction to this (and if it contains an introduction to this that isn't decent, I'd think it's not a very good book). While the standard deterministic algorithm for this takes quadratic time, there is a randomized nearly-linear time algorithm. See Seress's book "Permutation Group Algorithms," Chapter 4 (the nearly-linear time Monte Carlo algorithm is Theorem 4.5.5).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.