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

10

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 .RR=STSSTRS

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

Anthony Labarre
źródło

Odpowiedzi:

1

Jeśli przechowujesz przypadkowe permutacje z prawdopodobieństwem będziesz potrzebował Bitów na permutację, złożoność Kołmogorowa to dyktuje. log2(n!)12log2(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) .Sn

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 ! )log2(OEIS_A186202(n))log2(n!)

wprowadź opis zdjęcia tutaj

Chad Brewbaker
źródło