Encoding sets of permutations with a generating set and a set of excluded elements

Question

Polynomial-time algorithms are known for finding generating sets of permutation groups, which is interesting since we can then represent those groups succinctly without giving up on polynomial-time algorithms for answering many interesting questions related to these groups.

However, we may sometimes be interested in a set $R$ of permutations that does not form a group, so that set would be represented by $R=\langle S\rangle \setminus T$, where $\langle S\rangle$ is the group generated by a set $S$ of generators and $T$ is a set of permutations that are not in $R$, instead of just $\langle S\rangle$.

Has any work been done on computing such an encoding in the form of a pair $\{S,T\}$, possibly with the additional, natural goal of minimising $|S|+|T|$?

Answer 1

If you are storing random permutations with probability ${1\over2}$ then you are going to need $log_{2}(n!)$ bits per permutation, Kolmogorov complexity dictates it.

If the distribution is non-random it depends.

To understand the state space it might help to look at http://oeis.org/A186202 , the size of any min dominating set over $S_{n}$ using a monogenic inclusion relation between permutations (ignoring the identity which is in all subgroups).

You can encode the relevant prime order permutations in $log_{2}( OEIS\_A186202(n) )$ bits each. That will give you some savings over the usual $log_{2}(n!)$ needed for a random permuation.