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|$?


1 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.

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.