<p>The most efficient (and also simplest) algorithms for this are based on the notion of a <a href="https://en.wikipedia.org/wiki/Strong_generating_set" rel="noreferrer">strong generating set</a>, introduced by Sims. Strong generating sets can be computed efficiently using the <a href="https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm" rel="noreferrer">Schreier-Sims algorithm</a>. 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).</p>

CC BY-SA 3.0
2017-11-08T04:07:15.260Z
2017-11-08T04:07:15.260Z
Joshua Grochow
<p>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?</p>

CC BY-SA 3.0
2017-11-06T14:32:01.447Z
Don't think there are efficient algorithms for doing this in a classical setting
Samuel Schlesinger
CC BY-SA 3.0
2017-11-06T18:26:43.127Z
I doubt that since there at least one such algorithm in [Polynomial-time algorithms for permutation groups](http://ieeexplore.ieee.org/document/4567802/?reload=true). What is asked here is maybe some general overview of existing algorithms and their key ideas.
Oleksandr  Kulkov
CC BY-SA 3.0
2017-11-07T23:55:34.810Z
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/on-topic] says, "Try to make your question interesting for others by providing some background knowledge. Remember, questions should be based on knowledge sharing".
D.W.
<ds.algorithms><permutations>
Computing size of permutation group from generators
Oleksandr  Kulkov
# Computing size of permutation group from generators

(Asked by: username_0 on 2017-11-05)

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?

**Tags:** ds.algorithms, permutations

> **Comments:**
> **username_1**: Don't think there are efficient algorithms for doing this in a classical setting  
> **username_0**: I doubt that since there at least one such algorithm in [Polynomial-time algorithms for permutation groups](http://ieeexplore.ieee.org/document/4567802/?reload=true). What is asked here is maybe some general overview of existing algorithms and their key ideas.  
> **username_2**: 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/on-topic] says, "Try to make your question interesting for others by providing some background knowledge. Remember, questions should be based on knowledge sharing".  

---

## 1 answers

### Answer by username_3 on 2017-11-08. Score: 7 | Accepted answer

The most efficient (and also simplest) algorithms for this are based on the notion of a [strong generating set](https://en.wikipedia.org/wiki/Strong_generating_set), introduced by Sims. Strong generating sets can be computed efficiently using the [Schreier-Sims algorithm](https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_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).


---

