Существуют эффективные структуры данных для представления заданных разделов. Эти структуры данных имеют хорошие временные сложности для таких операций, как Union и Find, но они не особенно эффективны в использовании.
Что такое эффективный для пространства способ представления раздела набора?
Вот одна из возможных отправных точек:
Я знаю , что количество разделов набора с элементами , в -го номер Bell . Таким образом, оптимальной пространственной сложностью для представления разбиения множества с элементами является бит. Чтобы найти такое представление, мы могли бы искать взаимно-однозначное соответствие между (набором разделов набора из элементов) и (набором целых чисел от до ).
Есть ли такое отображение, которое эффективно вычислять? Под «эффективным» я подразумеваю, что я хочу преобразовать это компактное представление в / из простого в обращении представления (такого как список списков) во временном полиноме по или .
Ответы:
Вы можете использовать способ получения формулы кодирования ниже, чтобы найти кодировку: Это доказывается с учетом количества других элементов в детали, содержащей элемент . Если их , то у нас есть для них и для разделения остальных.Bn+1=∑k=0n(nk)Bk. n+1 n−k (nn−k)=(nk) Bk
Используя это, мы можем дать рекурсивный алгоритм для преобразования любого раздела в число в диапазоне . Я предполагаю, что у вас уже есть способ преобразования подмножества размера из в число в диапазоне (такой алгоритм может быть разработан таким же образом, используя повторение Паскаля ).n+1 0,…,Bn+1−1 k {1,…,n} 0,…,(nk)−1 (nk)=(n−1k)+(n−1k−1)
Предположим, что часть, содержащая содержит других элементов. Найдите их код . Вычислить раздел , "сжав" все оставшиеся элементы до этого диапазона. Рекурсивно вычислить его код . Новый код:n+1 k C1 {1,…,n−k} C2 C=∑l=0n−k−1(nl)Bl+C1Bn−k+C2.
В другом направлении, учитывая код , найдите уникальное такое, что и определить Поскольку , его можно записать как , где . Теперь кодирует элементы в части, содержащей , а кодирует разбиениеC k ∑l=0n−k−1(nl)Bl≤C<∑l=0n−k(nl)Bl, C′=C−∑l=0n−k−1(nl)Bl. 0≤C′<(nk)Bn−k C1Bn−k+C2 0≤C2<Bn−k C1 n+1 C2 {1,…,n−k} , который может быть декодирован рекурсивно. Чтобы завершить декодирование, вы должны «разархивировать» последний раздел, чтобы он содержал все элементы, отсутствующие в части, содержащей .n+1
Вот как использовать ту же технику для рекурсивного кодирования подмножества размером размера . Если то код равен , поэтому предположим, что . Если то пусть - это код как подмножество размера из ; код - . Если то пусть будет кодом , как подмножество размера из ; кодS {1,…,n} k k=0 0 k>0 n∈S C1 S∖{n} k−1 {1,…,n−1} S C1 n∉S C1 S k {1,…,n−1} S это .C1+(n−1k−1)
Чтобы декодировать код , есть два случая. Если то декодировать подмножество из размера чей код , и вывести . В противном случае, декодировать подмножество из размера которой код , и выход .C C<(n−1k−1) S′ {1,…,n−1} k−1 C S′∪{n} S′ {1,…,n−1} k C−(n−1k−1) S′
источник