Existen estructuras de datos eficientes para representar particiones establecidas. Estas estructuras de datos tienen buenas complejidades de tiempo para operaciones como Union y Find, pero no son particularmente eficientes en cuanto al espacio.
¿Cuál es una forma de espacio eficiente para representar una partición de un conjunto?
Aquí hay un posible punto de partida:
Sé que el número de particiones de un conjunto con elementos es , el número -ésima campana . Entonces, la complejidad espacial óptima para representar una partición de un conjunto con elementos es bits. Para encontrar dicha representación, podríamos buscar un mapeo uno a uno entre (el conjunto de particiones de un conjunto de elementos) y (el conjunto de enteros de a ).B N Nlog 2 ( B N ) N 1 B N
¿Existe tal mapeo que sea eficiente para calcular? Lo que quiero decir con "eficiente" es que quiero convertir esta representación compacta a / de una representación fácil de manipular (como una lista de listas) en un polinomio temporal en o .log 2 ( B N )
Respuestas:
Puede utilizar la forma en que se deriva la siguiente fórmula de recurrencia para encontrar su codificación: Esto se prueba considerando cuántos otros elementos hay en la parte que contiene el elemento . Si hay de estos, entonces tenemos opciones para ellos, y opciones para dividir el resto.Bn+1=∑k=0n(nk)Bk. n+1 n−k (nn−k)=(nk) Bk
Con esto, podemos dar un algoritmo recursivo para convertir cualquier partición de en un número en el rango . Supongo que ya tiene una forma de convertir un subconjunto de tamaño de a un número en el rango (tal algoritmo puede idearse de la misma manera usando la recurrencia de Pascal ).n+1 0,…,Bn+1−1 k {1,…,n} 0,…,(nk)−1 (nk)=(n−1k)+(n−1k−1)
Suponga que la parte que contiene contiene otros elementos. Encuentra su código . Calcule una partición de "comprimiendo" todos los elementos restantes en ese rango. Calcular recursivamente su código . El nuevo código esn+1 k C1 {1,…,n−k} C2 C=∑l=0n−k−1(nl)Bl+C1Bn−k+C2.
En la otra dirección, dado un código , encuentre la única tal que y defina Como , puede escribirse como , donde . Ahora codifica los elementos en la parte que contiene , y codifica una partición deC 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} , que se puede decodificar recursivamente. Para completar la decodificación, debe "descomprimir" la última partición para que contenga todo el elemento que no aparece en la parte que contiene .n+1
Aquí se explica cómo usar la misma técnica para codificar un subconjunto de de tamaño , recursivamente. Si entonces el código es , entonces supongamos que . Si entonces sea un código de , como un subconjunto de tamaño de ; El código de es . Si entonces deje que sea un código de , como un subconjunto de tamaño de ; el código deS {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 es .C1+(n−1k−1)
Para decodificar un código , hay dos casos. Si entonces decodifica un subconjunto de de tamaño cuyo código es y la salida . De lo contrario, decodifique un subconjunto de de tamaño cuyo código sea , y envíe .C C<(n−1k−1) S′ {1,…,n−1} k−1 C S′∪{n} S′ {1,…,n−1} k C−(n−1k−1) S′
fuente