Apa cara yang ringkas untuk merepresentasikan partisi dari set?

Ada struktur data yang efisien untuk mewakili sekumpulan partisi. Struktur data ini memiliki kompleksitas waktu yang baik untuk operasi seperti Union dan Find, tetapi mereka tidak terlalu efisien dalam ruang.

Apa cara hemat-ruang untuk merepresentasikan partisi sekumpulan?

Inilah satu titik awal yang memungkinkan:

Saya tahu bahwa jumlah partisi set dengan elemen adalah , nomor Bell ke- . Jadi kompleksitas ruang optimal untuk merepresentasikan partisi set dengan elemen adalah bits. Untuk menemukan representasi seperti itu, kita bisa mencari pemetaan satu-ke-satu antara (himpunan partisi dari himpunan elemen ) dan (himpunan bilangan bulat dari hingga ).$N$$B_N$$N$$N$$\log_2(B_N)$$N$$1$$B_N$

Apakah ada pemetaan yang efisien untuk dihitung? Yang saya maksud dengan "efisien" adalah bahwa saya ingin mengubah representasi kompak ini menjadi / dari representasi yang mudah dimanipulasi (seperti daftar daftar) dalam polinomial waktu dalam atau .$N$$\log_2(B_N)$

Anda dapat menggunakan cara rumus perulangan di bawah ini diperoleh untuk menemukan penyandian Anda: Ini dibuktikan dengan mempertimbangkan berapa banyak elemen lain di bagian yang mengandung elemen . Jika ada di antaranya, maka kita memiliki pilihan , dan pilihan untuk mempartisi sisanya.

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

Dengan menggunakan ini, kita dapat memberikan algoritma rekursif untuk mengubah partisi menjadi angka dalam rentang . Saya berasumsi Anda sudah memiliki cara untuk mengubah subset ukuran dari ke angka dalam rentang (algoritma seperti itu dapat dibuat dengan cara yang sama menggunakan perulangan 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}$

Misalkan bagian yang mengandung mengandung elemen lainnya. Temukan kode mereka . Hitung partisi dengan "mengompresi" semua elemen yang tersisa ke rentang itu. Menghitung kode . Kode baru adalah$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.$$

Di arah lain, diberi kode , temukan unik sehingga dan tentukan Karena , dapat ditulis sebagai , di mana . Sekarang mengkode elemen-elemen di bagian yang berisi , dan mengkode partisi dari$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\}$, yang dapat diterjemahkan secara rekursif. Untuk menyelesaikan decoding, Anda harus "membuka kompresi" partisi terakhir sehingga berisi semua elemen yang tidak muncul di bagian yang berisi .$n+1$

---

Berikut adalah cara menggunakan teknik yang sama untuk menyandikan subset dari dengan ukuran , secara rekursif. Jika maka kodenya adalah , jadi anggaplah . Jika maka biarkan menjadi kode , sebagai bagian dari ukuran dari ; kode adalah . Jika maka biarkan menjadi kode , sebagai bagian dari ukuran dari ; kode$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$adalah .$C_1 + \binom{n-1}{k-1}$

Untuk memecahkan kode , ada dua kasus. Jika kemudian mendekodekan subset dari dengan ukuran yang kodenya , dan menghasilkan . Jika tidak, decode subset dari dengan ukuran yang kodenya adalah , dan output .$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'$