Jaki jest kompaktowy sposób reprezentowania partycji zestawu?

Istnieją wydajne struktury danych do reprezentowania ustawionych partycji. Te struktury danych charakteryzują się dużą złożonością czasową dla operacji takich jak Union i Find, ale nie są szczególnie efektywne pod względem przestrzeni.

Jaki jest oszczędny przestrzennie sposób reprezentowania partycji zestawu?

Oto jeden z możliwych punktów wyjścia:

Wiem, że liczba partycji zestawu z $N$ elementami to , numer ty Bell . Zatem optymalna złożoność przestrzeni do reprezentowania partycji zestawu z elementami to bitów. Aby znaleźć taką reprezentację, moglibyśmy poszukać odwzorowania jeden na jednego między (zestawem partycji zestawu elementów) a (zestawem liczb całkowitych od do ).$B_N$$N$log 2 ( B N ) N 1 B $N$$\log_2(B_N)$$N$$1$$B_N$

Czy istnieje takie mapowanie, które jest wydajne w obliczeniach? Rozumiem przez „wydajny” to, że chcę przekonwertować tę zwartą reprezentację na / z łatwej w obsłudze reprezentacji (takiej jak lista list) w wielomianie czasowym w lub .log 2 ( B N$N$$\log_2(B_N)$

Aby znaleźć kodowanie, możesz użyć sposobu wyprowadzenia poniższej formuły rekurencyjnej:

$$B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k.$$ Dowodzi tego rozważenie, ile innych elementów znajduje się w części zawierającej element$n+1$. Jeśli jest ich$n-k$, to mamy$\binom{n}{n-k} = \binom{n}{k}$ wybory dla nich, i$B_k$wybory dla podziału pozostałych.

Korzystając z tego, możemy podać algorytm rekurencyjny do konwersji dowolnej partycji $n+1$ na liczbę z zakresu $0,\ldots,B_{n+1}-1$ . Zakładam, że masz już sposób konwertowania podzbiór rozmiarze $k$ z $\{1,\ldots,n\}$ na liczbę w zakresie $0,\ldots,\binom{n}{k}-1$(taki algorytm można opracować w ten sam sposób, korzystając z powtarzalności Pascala$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ ).

Załóżmy, że część zawierająca $n+1$ zawiera $k$ innych elementów. Znajdź ich kod $C_1$ . Oblicz partycję $\{1,\ldots,n-k\}$ , „kompresując” wszystkie pozostałe elementy do tego zakresu. Rekurencyjnie oblicz kod $C_2$ . Nowy kod to

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

W przeciwnym kierunku, biorąc pod uwagę kod $C$ , znajdź unikalne $k$ takie, że

$$\sum_{l=0}^{n-k-1} \binom{n}{l} B_l \leq C < \sum_{l=0}^{n-k} \binom{n}{l} B_l,$$ i określają $$C' = C - \sum_{l=0}^{n-k-1} \binom{n}{l} B_l.$$ Ponieważ$0 \leq C' < \binom{n}{k} B_{n-k}$, można zapisać jako$C_1 B_{n-k} + C_2$, gdzie$0 \leq C_2 < B_{n-k}$. Teraz$C_1$koduje elementy w części zawierającej$n+1$, a$C_2$koduje partycję$\{1,\ldots,n-k\}$, które można dekodować rekurencyjnie. Aby zakończyć dekodowanie, musisz „zdekompresować” drugą partycję, aby zawierała cały element nie pojawiający się w części zawierającej $n+1$ .

---

Oto jak zastosować tę samą technikę do rekurencyjnego kodowania podzbioru $S$ wielkości $\{1,\ldots,n\}$ o rozmiarze $k$ . Jeśli $k=0$ wówczas kod wynosi $0$ , więc załóżmy, że $k>0$ . Jeśli $n \in S$ niech $C_1$ będzie kodem $S \setminus \{n\}$ , jako podzbiorem wielkości $k-1$ z $\{1,\ldots,n-1\}$; kod $S$ to $C_1$ . Jeśli $n \notin S$ niech $C_1$ będzie kod $S$ , jako podzbiór o rozmiarze $k$ o $\{1,\ldots,n-1\}$ ; kod $S$ to $C_1 + \binom{n-1}{k-1}$ .

Aby zdekodować kod $C$ , istnieją dwa przypadki. Jeśli $C < \binom{n-1}{k-1}$ a następnie zdekoduj podzbiór$S'$o wartości$\{1,\ldots,n-1\}$o rozmiarze$k-1$którego kodem jest$C$, iwyślij$S' \cup \{n\}$. W przeciwnym razie zdekoduj podzbiór$S'$o wartości$\{1,\ldots,n-1\}$o rozmiarze$k$którego kod to$C - \binom{n-1}{k-1}$ i wyjście$S'$.