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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Don't think there are efficient algorithms for doing this in a classical setting $\endgroup$– Samuel SchlesingerNov 6, 2017 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 KulkovNov 6, 2017 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, 2017 at 23:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
answered Nov 8, 2017 at 4:07