Ce qui est une façon compacte pour représenter une partition d'un ensemble?

Question

Il existe données efficaces structures pour représenter ensemble partitions. Ces structures de données ont de bonnes complexités de temps pour les opérations comme l'Union et trouver, mais ils ne sont pas particulièrement efficaces espace.

Qu'est-ce qu'un moyen efficace d'espace pour représenter une partition d'un ensemble?

Voici un point de départ possible:

Je sais que le nombre de partitions d'un ensemble d'éléments $ n $ est $ B_N $, le N -ième $ $ de Bell numéro . Ainsi, l'espace optimal complexité pour représenter une partition d'un ensemble avec des éléments de $ $ N est $ \ Log_2 (B_N) bits $. Pour trouver une telle représentation, nous pourrions chercher un un-à-un entre (l'ensemble des partitions d'un ensemble d'éléments $ n $) et (L'ensemble des nombres entiers de 1 $ à $ B_N $).

Y at-il une telle cartographie qui est efficace pour calculer? Ce que je veux dire par « Efficace » est que je veux convertir cette représentation compacte à / d'une représentation facile à manipuler (par exemple une liste de listes) dans le temps polynôme $ N $ ou $ \ log_2 (B_N) $.

Answer 1

Vous pouvez utiliser la manière que la formule de récurrence ci-dessous est dérivé de trouver l'encodage: $$ B_ {n + 1} = \ sum_ {k = 0} ^ n \ binom {n} {k} B_k. $$ Ceci est prouvé par combien d'autres considèrent les éléments sont dans la partie contenant l'élément $ n + 1 $. S'il y a $ n-k $ de ceux-ci, nous avons $ \ binom {n} {n-k} = \ Binom {n} {k} $ choix pour eux, et les choix $ B_k $ pour partitionner le reste.

Avec cela, nous pouvons donner un algorithme récursif pour convertir une partition de n $ + 1 $ à un nombre compris entre 0 $, \ ldots, B_ {n + 1} $ -1. Je suppose que vous avez déjà un moyen de convertir un sous-ensemble de taille $ k $ de $ \ {1, \ ldots, n \} $ à un nombre compris entre 0 $, \ ldots, \ binom {n} {k} -1 $ (un tel algorithme peut être conçu de la même manière à l'aide de Pascal récidive $ \ binom {n} {k} = \ binom {n-1} {k} + \ binom {n-1} {k-1} $) .

Supposons que la partie contenant n + 1 $ $ $ k $ contient d'autres éléments. Trouvez leur code $ C_1 $. Calculer une partition de $ \ {1, \ ldots, n-k \} $ par "compression" tous les autres éléments à cette gamme. Récursive calculer son code $ C_2 $. Le nouveau code est C = $$ \ sum_ {l = 0} ^ {k-1} \ binom {n} {l} B_L + C_1 B_k + C_2. $$

Dans l'autre sens, étant donné un code $ C $, trouver k unique $ $ tel que $$ \ sum_ {l = 0} ^ {k-1} \ binom {n} {l} B_L \ leq C <\ sum_ {l = 0} ^ k \ binom {n} {l} B_L, $$ et définir $$ C »= C - \ sum_ {l = 0} ^ {k-1} \ binom {n} {l} B_L. $$ Depuis $ 0 \ leq C »<\ binom {n} {k} B_k $, il peut être écrit $ C_1 B_k + C_2 $, où $ 0 \ leq C_2

---

Voici comment utiliser la même technique pour coder un sous-ensemble $ S $ de $ \ {1, \ ldots, n \} $ de taille $ k $, récursive. Si $ k = 0 $, alors le code est $ 0 $, alors supposons k $> 0 $. Si $ n \ in S $, alors laissez C_1 $ $ un code de $ S \ setminus \ {n \} $, comme un sous-ensemble de taille $ k-1 $ de $ \ {1, \ ldots, n-1 \ } $; le code de $ S $ est $ C_1 $. Si $ n \ Notin S $, alors laissez C_1 $ $ un code de $ S $, comme un sous-ensemble de taille $ k $ de $ \ {1, \ ldots, n-1 \} $; le code de $ S $ est $ C_1 + \ {binom n-1} {k-1} $.

Pour décoder un code $ C $, il y a deux cas. Si $ C <\ binom {n-1} {k-1} $ décode alors un sous-ensemble $ S '$ de $ \ {1, \ ldots, n-1 \} $ de taille k-1 $ dont le code est $ C $, et la sortie $ S \ cup \ {n \} $. Dans le cas contraire, décoder un sous-ensemble $ S '$ de $ \ {1, \ ldots, n-1 \} $ de taille $ k $ dont le code est $ C - \ binom {n-1} {k-1} $, et $ 'sortie $ S.