O que é uma maneira compacta de representar uma partição de um conjunto?

11

Existem estruturas de dados eficientes para representar partições definidas. Essas estruturas de dados têm boas complexidades de tempo para operações como Union e Find, mas não são particularmente eficientes em termos de espaço.

O que é uma maneira eficiente de espaço para representar uma partição de um conjunto?

Aqui está um possível ponto de partida:

Eu sei que o número de partições de um conjunto com elementos é , o número sino . Portanto, a complexidade ideal de espaço para representar uma partição de um conjunto com elementos é de bits. Para encontrar essa representação, poderíamos procurar um mapeamento individual entre (o conjunto de partições de um conjunto de elementos) e (o conjunto de números inteiros de a ).B N N N log 2 ( B N ) N 1 B NNBNNNlog2(BN)N1BN

Existe um mapeamento eficiente para calcular? O que quero dizer com "eficiente" é que desejo converter essa representação compacta para / de uma representação fácil de manipular (como uma lista de listas) no polinômio de tempo em ou .log 2 ( B N )Nlog2(BN)

cberzan
fonte
imaginando, até que ponto estar da codificação ingênua / natural de apenas atribuir números inteiros exclusivos a cada elemento do conjunto em que o número inteiro representa a partição #? talvez "não é muita diferença" ...log2(BN)
vzn

Respostas:

7

Você pode usar o modo como a fórmula de recorrência abaixo é derivada para localizar sua codificação: Isso é comprovado considerando-se quantos outros elementos existem na parte que contém o elemento . Se houver destes, então temos para eles e para particionar o restante.

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

Usando isso, podemos fornecer um algoritmo recursivo para converter qualquer partição de em um número no intervalo . Suponho que você já tenha uma maneira de converter um subconjunto de tamanho de em um número no intervalo (um algoritmo desse tipo pode ser criado da mesma maneira usando a recorrência de Pascal ).n+1 10 0,,Bn+1 1-1 1k{1 1,,n}0 0,,(nk)-1 1(nk)=(n-1 1k)+(n-1 1k-1 1)

Suponha que a parte que contém contenha outros elementos. Encontre o código . Calcule uma partição de "compactando" todos os elementos restantes para esse intervalo. recursivamente seu código . O novo código én+1 1kC1 1{1 1,,n-k}C2

C=eu=0 0n-k-1 1(neu)Beu+C1 1Bn-k+C2.

Na outra direção, dado um código , encontre o único tal que e defina Desde , ele pode ser escrito como , onde . Agora codifica os elementos na parte que contém e codifica uma partição deCk

l=0nk1(nl)BlC<l=0nk(nl)Bl,
C=Cl=0nk1(nl)Bl.
0C<(nk)BnkC1Bnk+C20C2<BnkC1n+1C2{1,,nk}n+1, que pode ser decodificado recursivamente. Para concluir a decodificação, é necessário "descompactar" a última partição para que ela contenha todo o elemento que não aparece na parte que contém .n+1


Aqui está como usar a mesma técnica para codificar um subconjunto de de tamanho , recursivamente. Se , o código é , então suponha que . Se , deixe ser um código de , como um subconjunto do tamanho de ; o código de é . Se , deixe ser um código de , como um subconjunto de tamanho de ; o código deS{1,,n}kk=00k>0nSC1S{n}k1{1,,n1}SC1 1nSC1 1Sk{1,,n-1 1}Sé .C1 1+(n-1 1k-1 1)

Para decodificar um código , existem dois casos. Se , decodifique um subconjunto de de tamanho cujo código é , e produza . Caso contrário, decodifique um subconjunto de de tamanho cujo código é e faça a saída .CC<(n1k1)S{1,,n1}k1CS{n}S{1,,n1}kC(n1k1)S

Yuval Filmus
fonte
Excelente resposta; obrigado. Bug menor: no esboço de prova da fórmula de recorrência no topo, acho que você quer dizer "existem desses" em vez de "existem desses" - então os elementos restantes podem ser particionados da maneira . k k B knkkkBk
precisa