Was ist eine kompakte Art, eine Partition einer Menge darzustellen?

Es gibt effiziente Datenstrukturen zur Darstellung festgelegter Partitionen. Diese Datenstrukturen weisen eine gute zeitliche Komplexität für Operationen wie Union und Find auf, sind jedoch nicht besonders platzsparend.

Was ist eine platzsparende Möglichkeit, eine Partition einer Menge darzustellen?

Hier ist ein möglicher Ausgangspunkt:

Ich weiß , dass die Anzahl der Partitionen eines Satzes mit Elementen ist , die - ten Bell - Nummer . Die optimale Raumkomplexität für die Darstellung einer Partition einer Menge mit Elementen beträgt also Bits. Um eine solche Darstellung zu finden, könnten wir nach einer Eins-zu-Eins-Zuordnung zwischen (der Menge von Partitionen einer Menge von Elementen) und (der Menge von ganzen Zahlen von bis ) .B N N N log 2 ( B N ) N 1 B $N$$B_N$$N$$N$$\log_2(B_N)$$N$$1$$B_N$

Gibt es eine solche Zuordnung, die effizient zu berechnen ist? Was ich unter "effizient" verstehe, ist, dass ich diese kompakte Darstellung in eine einfach zu manipulierende Darstellung (z. B. eine Liste von Listen) im in oder .log 2 ( B N$N$$\log_2(B_N)$

Sie können die folgende Wiederholungsformel verwenden, um Ihre Codierung zu ermitteln: Dies wird bewiesen, indem berücksichtigt wird, wie viele andere Elemente sich in dem Teil befinden, der das Element . Wenn es davon gibt, haben wir Auswahlmöglichkeiten für sie und Auswahlmöglichkeiten für die Partitionierung des Restes.

$$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$

Auf diese Weise können wir einen rekursiven Algorithmus angeben, um eine beliebige Partition von in eine Zahl im Bereich umzuwandeln . Ich gehe davon aus, dass Sie bereits eine Möglichkeit haben, eine Teilmenge der Größe von in eine Zahl im Bereich (einen solchen Algorithmus) zu konvertieren kann auf die gleiche Weise mit Pascals Wiederholung entwickelt werden ).$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}$

Angenommen, der Teil, der enthält, enthält andere Elemente. Finden Sie ihren Code . Berechnen Sie eine Partition von indem Sie alle verbleibenden Elemente auf diesen Bereich "komprimieren". Berechnen Sie rekursiv den Code . Der neue Code lautet$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.$$

In der anderen Richtung finden Sie bei gegebenem Code das eindeutige so, dass und definiere Da , kann es als , wobei . Jetzt codiert die Elemente in dem Teil, der , und codiert eine Partition von$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\}$, die rekursiv dekodiert werden kann. Um die Dekodierung abzuschließen, müssen Sie die letztere Partition "dekomprimieren", damit sie alle Elemente enthält, die nicht in dem Teil enthalten sind, der .$n+1$

---

Hier erfahren Sie, wie Sie mit derselben Technik eine Teilmenge von der Größe rekursiv codieren . Wenn ist der Code , also sei . Wenn dann sei ein Code von als Teilmenge der Größe von ; der Code von ist . Wenn dann sei ein Code von als Teilmenge der Größe von ; der Code von$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$ist .$C_1 + \binom{n-1}{k-1}$

Um einen Code zu dekodieren , gibt es zwei Fälle. Wenn dann decodiere eine Teilmenge von der Größe deren Code , und gebe . Andernfalls decodieren Sie eine Teilmenge von der Größe deren Code , und geben Sie .$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'$