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

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 $N$$B_N$$N$$N$$\log_2(B_N)$$N$$1$$B_N$

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 $\log_2(B_N)$ .

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.

$$B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k.$$ $n+1$$n-k$$\binom{n}{n-k} = \binom{n}{k}$$B_k$

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+1$$0,\ldots,B_{n+1}-1$$k$$\{1,\ldots,n\}$$0,\ldots,\binom{n}{k}-1$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$

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 est$n+1$$k$$C_1$$\{1,\ldots,n-k\}$$C_2$

$$C = \sum_{l=0}^{n-k-1} \binom{n}{l} B_l + C_1 B_{n-k} + C_2.$$

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 de$C$$k$

$$\sum_{l=0}^{n-k-1} \binom{n}{l} B_l \leq C < \sum_{l=0}^{n-k} \binom{n}{l} B_l,$$ $$C' = C - \sum_{l=0}^{n-k-1} \binom{n}{l} B_l.$$ $0 \leq C' < \binom{n}{k} B_{n-k}$$C_1 B_{n-k} + C_2$$0 \leq C_2 < B_{n-k}$$C_1$$n+1$$C_2$$\{1,\ldots,n-k\}$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 de$S$$\{1,\ldots,n\}$$k$$k=0$$0$$k>0$$n \in S$$C_1$$S \setminus \{n\}$$k-1$$\{1,\ldots,n-1\}$$S$$C_1$$n \notin S$$C_1$$S$$k$$\{1,\ldots,n-1\}$$S$est .$C_1 + \binom{n-1}{k-1}$

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 .$C$$C < \binom{n-1}{k-1}$$S'$$\{1,\ldots,n-1\}$$k-1$$C$$S' \cup \{n\}$$S'$$\{1,\ldots,n-1\}$$k$$C - \binom{n-1}{k-1}$$S'$