Codificando conjuntos de permutações com um conjunto gerador e um conjunto de elementos excluídos

Os algoritmos de tempo polinomial são conhecidos por encontrar conjuntos geradores de grupos de permutação, o que é interessante, pois podemos então representar esses grupos de maneira sucinta, sem desistir dos algoritmos de tempo polinomial para responder a muitas perguntas interessantes relacionadas a esses grupos.

Entretanto, às vezes podemos estar interessados ​​em um conjunto de permutações que não forma um grupo, de modo que esse conjunto seria representado por , em que é o grupo gerado por um set de geradores e é um conjunto de permutações que não estão em , em vez de apenas .$R$$R=\langle S\rangle \setminus T$$\langle S\rangle$$S$$T$$R$$\langle S\rangle$

Foi realizado algum trabalho sobre o cálculo dessa codificação na forma de um par , possivelmente com o objetivo natural adicional de minimizar?$\{S,T\}$$|S|+|T|$

Se você estiver armazenando permutações aleatórias com probabilidade , então você vai precisarlog2(n!)Bits por permutação, Kolmogorov complexidade ditames de TI.${1\over2}$$log_{2}(n!)$

Se a distribuição não for aleatória, depende.

$S_{n}$

$log_{2}( OEIS\_A186202(n) )$$log_{2}(n!)$