Encoding sets of permutations with a generating set and a set of excluded elements
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.