Kodowanie zestawów permutacji za pomocą zestawu generującego i zestawu elementów wykluczonych

Algorytmy czasu wielomianowego znane są ze znajdowania generujących zestawów grup permutacji, co jest interesujące, ponieważ możemy następnie przedstawić te grupy zwięźle, nie rezygnując z algorytmów czasu wielomianowego do odpowiedzi na wiele interesujących pytań związanych z tymi grupami.

Czasami jednak możemy być zainteresowani zestawem permutacji, który nie tworzy grupy, więc zestaw ten będzie reprezentowany przez , gdzie to grupa wygenerowana przez zestaw generatorów i to zestaw permutacji, które nie są w , zamiast po prostu .$R$$R=\langle S\rangle \setminus T$$\langle S\rangle$$S$$T$$R$$\langle S\rangle$

Czy wykonano jakąkolwiek pracę przy obliczaniu takiego kodowania w postaci pary , być może z dodatkowym, naturalnym celem minimalizacji?$\{S,T\}$$|S|+|T|$

Jeśli przechowujesz przypadkowe permutacje z prawdopodobieństwem będziesz potrzebował Bitów na permutację, złożoność Kołmogorowa to dyktuje. log2(n!${1\over2}$$log_{2}(n!)$

Jeśli rozkład jest nieprzypadkowy, zależy to.

Aby zrozumieć przestrzeń stanu, warto spojrzeć na http://oeis.org/A186202 , wielkość dowolnego min dominującego zestawu ponad stosując monogeniczną relację włączenia między permutacjami (ignorując tożsamość, która jest we wszystkich podgrupach) .$S_{n}$

Można zakodować odpowiednie permutacje zamówień głównych w bitach każdy. To da ci oszczędności w stosunku do zwykłego Potrzebnego do losowego permuacji.l o g 2 ( n ! $log_{2}( OEIS\_A186202(n) )$$log_{2}(n!)$