Qu'est-ce qu'un moyen compact de représenter une partition d'un ensemble?

11

Il existe des structures de données efficaces pour représenter les partitions définies. Ces structures de données présentent de bonnes complexités temporelles pour des opérations telles que Union et Find, mais elles ne sont pas particulièrement économes en espace.

Qu'est-ce qu'un moyen peu encombrant de représenter une partition d'un ensemble?

Voici un point de départ possible:

Je sais que le nombre de partitions d'un ensemble avec éléments est , le -ième numéro de Bell . Ainsi, la complexité optimale de l'espace pour représenter une partition d'un ensemble avec éléments est de bits. Pour trouver une telle représentation, nous pourrions rechercher un mappage un à un entre (l'ensemble des partitions d'un ensemble de éléments) et (l'ensemble des entiers de à ).B N N N log 2 ( B N ) N 1 B NNBNNNlog2(BN)N1BN

Existe-t-il une telle cartographie efficace à calculer? Ce que je veux dire par «efficace», c'est que je veux convertir cette représentation compacte en / à partir d'une représentation facile à manipuler (telle qu'une liste de listes) en polynôme temporel en N ou log2(BN) .

cberzan
la source
se demandant, à quelle distance pourrait-il être du codage naïf / naturel de simplement affecter des entiers uniques à chaque élément de l'ensemble où l'entier représente la partition #? c'est peut-être "pas tant de différence" ...log2(BN)
vzn

Réponses:

7

Vous pouvez utiliser la manière dont la formule de récurrence ci-dessous est dérivée pour trouver votre codage: Ceci est prouvé en considérant combien d'autres éléments se trouvent dans la partie contenant l'élément . S'il y en a , alors nous avons choix pour eux, et choix pour partitionner le reste.

Bn+1=k=0n(nk)Bk.
n+1nk(nnk)=(nk)Bk

En utilisant cela, nous pouvons donner un algorithme récursif pour convertir n'importe quelle partition de en un nombre dans la plage . Je suppose que vous avez déjà un moyen de convertir un sous-ensemble de taille de en un nombre compris dans la plage (un tel algorithme peut être conçu de la même manière en utilisant la récurrence de Pascal ).n+10,,Bn+11k{1,,n}0,,(nk)1(nk)=(n1k)+(n1k1)

Supposons que la partie contenant contient autres éléments. Trouvez leur code . Calculez une partition de en "compressant" tous les éléments restants dans cette plage. Calculer récursivement son code . Le nouveau code estn+1kC1{1,,nk}C2

C=l=0nk1(nl)Bl+C1Bnk+C2.

Dans l'autre sens, étant donné un code , trouvez l'unique tel que et définissez Puisque , il peut être écrit comme , où . Maintenant code les éléments dans la partie contenant , et code une partition deCk

l=0nk1(nl)BlC<l=0nk(nl)Bl,
C=Cl=0nk1(nl)Bl.
0C<(nk)BnkC1Bnk+C20C2<BnkC1n+1C2{1,,nk}n+1, qui peut être décodé récursivement. Pour terminer le décodage, vous devez "décompresser" cette dernière partition afin qu'elle contienne tout l'élément n'apparaissant pas dans la partie contenant .n+1


Voici comment utiliser la même technique pour encoder un sous-ensemble de de taille , récursivement. Si alors le code est , supposons donc . Si alors est un code de , comme un sous-ensemble de taille de ; le code de est . Si alors Soit un code de , comme un sous-ensemble de taille de ; le code deS{1,,n}kk=00k>0nSC1S{n}k1{1,,n1}SC1nSC1Sk{1,,n1}Sest .C1+(n1k1)

Pour décoder un code , il y a deux cas. Si alors décodez un sous-ensemble de de taille dont le code est , et sortez . Sinon, décodez un sous-ensemble de de taille dont le code est , et sortez .CC<(n1k1)S{1,,n1}k1CS{n}S{1,,n1}kC(n1k1)S

Yuval Filmus
la source
Excellente réponse; Merci. Bug mineur: dans l'esquisse de preuve pour la formule de récurrence en haut, je pense que vous voulez dire "il y a de ceux-ci" au lieu de "il y a de ceux-ci" - alors les éléments restants peuvent être partitionnés de manière . nkkkBk
cberzan