Encodage d'ensembles de permutations avec un groupe électrogène et un ensemble d'éléments exclus

Les algorithmes en temps polynomial sont connus pour trouver des groupes générateurs de groupes de permutation, ce qui est intéressant car nous pouvons alors représenter ces groupes de manière succincte sans renoncer aux algorithmes en temps polynomial pour répondre à de nombreuses questions intéressantes liées à ces groupes.

Cependant, nous pouvons parfois être intéressés par un ensemble de permutations qui ne forme pas un groupe, de sorte que cet ensemble serait représenté par , où est le groupe généré par un ensemble de générateurs et est un ensemble de permutations qui ne sont pas dans , au lieu de simplement .$R$$R=\langle S\rangle \setminus T$$\langle S\rangle$$S$$T$$R$$\langle S\rangle$

Des travaux ont-ils été effectués sur le calcul d'un tel encodage sous la forme d'une paire , éventuellement dans le but naturel supplémentaire de minimiser?$\{S,T\}$$|S|+|T|$

Si vous stockez des permutations aléatoires avec la probabilité alors vous aurez besoin de Bits par permutation, la complexité de Kolmogorov le dicte.${1\over2}$$log_{2}(n!)$

Si la distribution n'est pas aléatoire, cela dépend.

Pour comprendre l'espace d'état, il peut être utile de consulter http://oeis.org/A186202 , la taille de tout ensemble dominant dominant sur utilisant une relation d'inclusion monogénique entre permutations (en ignorant l'identité qui se trouve dans tous les sous-groupes) .$S_{n}$

Vous pouvez coder les permutations d'ordre premier pertinentes en bits chacun. Cela vous permettra de réaliser des économies par rapport au Habituel nécessaire pour une permutation aléatoire.l o g 2 ( n ! $log_{2}( OEIS\_A186202(n) )$$log_{2}(n!)$