# Generating Permutations with Given Set

Let $S_n$ be the set of all permutations that act on $1...n$. You are given a subset $P\subseteq S_n$, and you are to compute the size of the set $G(P) \subseteq S_n$, where $G(P)$ meets the following requirements:

1. $G(P)$ contains the identity permutation,
2. $P \subseteq G(P)$,
3. $G(P)$ is closed under taking inverses and multiplications (if $a, b \in G(P)$, then $ab \in G(P)$, if $a \in G(P)$, then $a^{-1} \in G(P)$),
4. $G(P)$ is a minimal possible set that meets requirements 1,2 and 3.

Is there a method or algorithm that can solve this?

• So in other words $G(P)$ is the subgroup of $S_n$ generated by $P$. The principal algorithm for this (which is polynomial-time) is known as the Schreier-Sims algorithm. – Derek Holt Apr 27 '12 at 8:30
• @Derek: poly time in what? The size of output? – Igor Rivin Apr 27 '12 at 15:42
• @Igor: Size of input. Lwins.Gafield just asked for the order of the group, but the output is actually a data structure, known as a base and strong generating set, that tells you the order, and also allows you to test quickly whether a given permutation in $S_n$ is in $G(P)$ and, if so, to express it as a word (more precisely a Straight Line Program) in $P$. Almost all other algorithms for computing structural information about $G(P)$ make use of this data structure. – Derek Holt Apr 27 '12 at 21:28