<p>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.</p>

<p>If the distribution is non-random it depends.</p>

<p>To understand the state space it might help to look at <a href="http://oeis.org/A186202" rel="nofollow noreferrer">http://oeis.org/A186202</a> , 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).</p>

<p>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.</p>

<p><img src="https://i.sstatic.net/JAsiA.png" alt="enter image description here"></p>

CC BY-SA 3.0
2014-02-28T15:17:51.540Z
2014-02-28T15:56:31.543Z
2014-02-28T15:56:31.543Z
Chad Brewbaker
<p>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.</p>

<p>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 <strong>not</strong> in $R$, instead of just $\langle S\rangle$. </p>

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

<permutations><gr.group-theory>
Encoding sets of permutations with a generating set and a set of excluded elements
Anthony Labarre
# Encoding sets of permutations with a generating set and a set of excluded elements

(Asked by: username_0 on 2014-02-28)

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

**Tags:** permutations, gr.group-theory

---

## 1 answers

### Answer by username_1 on 2014-02-28. Score: 2

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](https://i.sstatic.net/JAsiA.png)


---

