Was ist eine kompakte Möglichkeit, eine Partition eines Satzes darzustellen?

Question

Es gibt effiziente Datenstrukturen zur Darstellung von Set -Partitionen. Diese Datenstrukturen haben eine gute Zeitkomplexität für Operationen wie Union und Find, aber sie sind nicht besonders räumlich effizient.

Was ist eine platzeffiziente Möglichkeit, eine Partition eines Satzes darzustellen?

Hier ist ein möglicher Ausgangspunkt:

Ich weiß, dass die Anzahl der PartitionenVon einem Set mit $ n $ Elements ist $ b_n $, das $ n $ -TH Glockennummer. Die optimale Raumkomplexität für die Darstellung einer Partition eines Satzes mit $ n $ Elements ist also $ log_2 (b_n) $ bit. Um eine solche Darstellung zu finden, konnten wir nach einer Eins-zu-Eins-Zuordnung zwischen (dem Satz von Partitionen eines Set von $ n $ Elementen) und (dem Satz von Ganzzahlen von 1 $ bis $ B_N $) suchen.

Gibt es eine solche Zuordnung, die effizient zu berechnen ist? Was ich mit "effizient" meine, ist, dass ich diese kompakte Darstellung in / von einer leicht zu manipulierten Darstellung (z. B. eine Liste von Listen) in der Zeit Polynom in $ n $ oder $ log_2 (b_n) $ konvertieren möchte.

Answer 1

Sie können die Art und Weise verwenden, wie die folgende Rezidivformel abgeleitet ist, um Ihre Encodierung zu finden: $$ B_ {n+1} = sum_ {k = 0}^n binom {n} {k} b_k. $$ Dies wird bewiesen, wie viele andere Elemente im Teil des Elements $ n+1 $ enthalten sind. Wenn es $ nk $ von diesen gibt, dann haben wir $ binom {n} {nk} = binom {n} {k} $ Choices für sie und $ b_k $ Choices für die Partitionation des Restes.

Mit diesem können wir einen rekursiven Algorithmus angeben, um eine Partition von $ n+1 $ in eine Zahl im Bereich $ 0, ldots, B_ {n+1} -1 $ umzuwandeln. Ich nehme an, Sie haben bereits eine Möglichkeit, eine Teilmenge mit einer Größe $ k $ von $ {1, ldots, n } $ in eine Nummer im Bereich $ 0, ldots, binom {n} {k} -1 zu konvertieren $ (ein solcher Algorithmus kann auf die gleiche Weise unter Verwendung von Pascals Recurce $ binom {n} {k} = binom {n-1} {k} + binom {n-1} {k-1} $) entwickelt werden .

Angenommen, der Teil, der $ n+1 $ enthält, enthält $ k $ andere Elemente. Finden Sie ihren Code $ C_1 $. Berechnen Sie eine Partition von $ {1, ldots, nk } $, indem Sie alle verbleibenden Elemente zu diesem Bereich "komprimieren". Berumend seinen Code $ C_2 $ rekursiv berechnen. Der neue Code ist $$ c = sum_ {l = 0}^{k-1} binom {n} {l} b_l + c_1 b_k + c_2. $$

In der anderen Richtung finden Sie bei einem Code $ c $ das eindeutige $ k $ so, dass $$ sum_ {l = 0}^{k-1} binom {n} {l} b_l leq c < sum_ oder . $$ Da $ 0 Leq C '< binom {n} {k} b_k $, kann es als $ c_1 b_k + c_2 $ geschrieben werden, wobei $ 0 Leq C_2 <b_k $. Jetzt codiert $ C_1 $ die Elemente in dem Teil, das $ n+1 $ enthält, und $ C_2 $ codiert eine Partition von $ {1, ldots, nk } $, die rekursiv dekodiert werden kann. Um die Dekodierung zu vervollständigen, müssen Sie die letztere Partition "unkontrollieren", damit sie das gesamte Element enthält, das nicht in dem Teil $ n+1 $ enthält.

---

Hier erfahren Sie, wie Sie dieselbe Technik verwenden, um eine Untergruppe $ s $ $ {1, ldots, n } $ von Größe $ k $, rekursiv zu codieren. Wenn $ k = 0 $ ist, dann ist der Code $ 0 $, nehme an $ k> 0 $. Wenn $ n in s $ dann $ c_1 $ ein Code von $ S setminus {n } $ als Teilmenge der Größe $ k-1 $ $ {1, ldots, n-1 sein soll } $; Der Code von $ s $ ist $ c_1 $. Wenn $ n notin s $, dann sei $ c_1 $ ein Code von $ s $ als Teilmenge der Größe $ k $ von $ {1, ldots, n-1 } $; Der Code von $ s $ ist $ c_1 + binom {n-1} {k-1} $.

Um einen Code $ C $ zu dekodieren, gibt es zwei Fälle. Wenn $ c < binom {n-1} {k-1} $ ist, dekodieren Sie eine Untergruppe $ s '$ $ {1, ldots, n-1 } $ Größe $ k-1 $, deren Code ist $ C $ und Ausgabe $ S ' Cup {n } $. Andernfalls dekodieren Sie eine Untergruppe $ s '$ $ {1, ldots, n-1 } $ von Größe $ k $, deren Code $ c- binom {n-1} {k-1} $ und ist Ausgabe $ s '$.