Что такое компактный способ представления раздела множества?

11

Существуют эффективные структуры данных для представления заданных разделов. Эти структуры данных имеют хорошие временные сложности для таких операций, как Union и Find, но они не особенно эффективны в использовании.

Что такое эффективный для пространства способ представления раздела набора?

Вот одна из возможных отправных точек:

Я знаю , что количество разделов набора с элементами , в -го номер Bell . Таким образом, оптимальной пространственной сложностью для представления разбиения множества с элементами является бит. Чтобы найти такое представление, мы могли бы искать взаимно-однозначное соответствие между (набором разделов набора из элементов) и (набором целых чисел от до ).NBNNNlog2(BN)N1BN

Есть ли такое отображение, которое эффективно вычислять? Под «эффективным» я подразумеваю, что я хочу преобразовать это компактное представление в / из простого в обращении представления (такого как список списков) во временном полиноме по или .Nlog2(BN)

cberzan
источник
интересно, как далеко может быть от наивного / естественного кодирования простого присваивания уникальных целых чисел каждому элементу набора, где целое число представляет раздел #? может быть, это "не такая уж большая разница" ...log2(BN)
vzn

Ответы:

7

Вы можете использовать способ получения формулы кодирования ниже, чтобы найти кодировку: Это доказывается с учетом количества других элементов в детали, содержащей элемент . Если их , то у нас есть для них и для разделения остальных.

Bn+1=k=0n(nk)Bk.
n+1nk(nnk)=(nk)Bk

Используя это, мы можем дать рекурсивный алгоритм для преобразования любого раздела в число в диапазоне . Я предполагаю, что у вас уже есть способ преобразования подмножества размера из в число в диапазоне (такой алгоритм может быть разработан таким же образом, используя повторение Паскаля ).n+10,,Bn+11k{1,,n}0,,(nk)1(nk)=(n1k)+(n1k1)

Предположим, что часть, содержащая содержит других элементов. Найдите их код . Вычислить раздел , "сжав" все оставшиеся элементы до этого диапазона. Рекурсивно вычислить его код . Новый код:n+1kC1{1,,nk}C2

C=l=0nk1(nl)Bl+C1Bnk+C2.

В другом направлении, учитывая код , найдите уникальное такое, что и определить Поскольку , его можно записать как , где . Теперь кодирует элементы в части, содержащей , а кодирует разбиениеCk

l=0nk1(nl)BlC<l=0nk(nl)Bl,
C=Cl=0nk1(nl)Bl.
0C<(nk)BnkC1Bnk+C20C2<BnkC1n+1C2{1,,nk}, который может быть декодирован рекурсивно. Чтобы завершить декодирование, вы должны «разархивировать» последний раздел, чтобы он содержал все элементы, отсутствующие в части, содержащей .n+1


Вот как использовать ту же технику для рекурсивного кодирования подмножества размером размера . Если то код равен , поэтому предположим, что . Если то пусть - это код как подмножество размера из ; код - . Если то пусть будет кодом , как подмножество размера из ; кодS{1,,n}kk=00k>0nSC1S{n}k1{1,,n1}SC1nSC1Sk{1,,n1}Sэто .C1+(n1k1)

Чтобы декодировать код , есть два случая. Если то декодировать подмножество из размера чей код , и вывести . В противном случае, декодировать подмножество из размера которой код , и выход .CC<(n1k1)S{1,,n1}k1CS{n}S{1,,n1}kC(n1k1)S

Юваль Фильмус
источник
Отличный ответ; благодарю вас. Небольшая ошибка: в наброске доказательства для формулы повторения вверху, я думаю, вы имеете в виду «есть из них» вместо «есть из них» - тогда оставшиеся элементов могут быть разделены способами , nkkkBk
cberzan