data-structures - teoria - tipos de conjuntos

Colección de conjuntos que no contienen conjuntos que son un subconjunto de otro en la colección (4)

Estoy buscando una estructura de datos abstractos que represente una colección de conjuntos de modo que ningún conjunto en la colección sea un subconjunto de otro conjunto en la colección.

Esto significa que en la inserción se cumplirán las siguientes condiciones:

A. Insertar un elemento que ya es un subconjunto de otro elemento devolverá la colección original.

B. Insertar un elemento que es un superconjunto de cualquier otro elemento dará como resultado una colección con el superconjunto añadido y los subconjuntos eliminados.

Asumiendo un orden en los elementos del conjunto, se puede usar un árbol de prefijos para representar la colección. Esto permite que la condición A se maneje muy rápidamente (es decir, ya no es necesario verificar la condición de lo que sería para insertar el subconjunto), sin embargo, cumplir con la condición B lleva tiempo.

Me pregunto si hay una estructura de datos que permita que B también se cumpla rápidamente.

Una idea trivial, que funcionará en O (K) donde K es el tamaño del elemento que se agrega.

mantén los sets de la forma que quieras
mantener el mapa de set_id -> set_size
mantener el mapa del objeto -> set_id

ambos A y B son O (K).

El enfoque trivial sería mantener una lista de conjuntos y realizar una búsqueda lineal a través de ese para cada conjunto entrante (prueba si el entrante es un subconjunto).

Obviamente, esto se ejecuta en el tiempo O (n) para la búsqueda lineal y posiblemente en el tamaño O (m) para el tamaño del conjunto entrante. Por lo tanto, O (n * m) tiempo total (número de conjuntos frente al tamaño de cada conjunto).

La optimización más obvia, por supuesto, es indexar en tamaños de conjunto. Luego solo prueba cada conjunto entrante frente a aquellos que son de igual o mayor tamaño. (Un conjunto no puede ser un subconjunto de un conjunto más pequeño, ¡duh!).

La próxima optimización que viene a la mente es crear en el índice de elementos. Por lo tanto, para cada conjunto entrante, encontrará la intersección de cada conjunto que contiene cada uno de los elementos. En otras palabras, si para el conjunto entrante {a, b, c}, encontramos que el elemento {a} existe en los conjuntos A, B y D, el elemento {b} existe en B, E y F, y {c} existe en A, B y Z ... entonces el conjunto entrante es un subconjunto de B (la intersección de {A, B, D}, {B, E, F} y {A, B, Z}).

Entonces, eso me parece una complejidad O (m * log (n)). (Tenemos que realizar búsquedas hash en cada elemento de cada conjunto entrante). Las inserciones también deben estar en el mismo orden (insertando la ID del nuevo conjunto en cada uno de los mapas del elemento). (En el análisis Big-O 2 * O (m log (n)) se reduce a O (m log (n)), por supuesto.

Si los miembros individuales de sus conjuntos A, B, ... se asignan a números primos distintos (y relativamente), y junto a cada conjunto almacenan el producto de todos los miembros como p (A), p (B), etc. subconjuntos y superconjuntos pueden encontrarse si p (X) es un factor de p (Y) o viceversa.

Podrías terminar con algunos números muy grandes, supongo, pero funciona en teoría.

Por ejemplo:

si [abcd] -> [2 3 5 7], p (abc) = 30, p (abd) = 42, p (bc) = 15, p (abcd) = 210

¡Qué sitio más tonto! Ahora me he registrado, por lo que a su debido tiempo podré comentar sobre cosas de ayer. Hasta entonces, sin embargo ...

@Stephen C: aunque creo que mi inglés es adecuado, parece que he adquirido un explicador: sin embargo, ha perdido fragmentos, y su comentario debería decir lo siguiente:

@Stephen C: encontrar los factores de un número arbitrario es de hecho NP completo, pero no relevante aquí. El problema es si el menor de dos números divide exactamente el más grande, una operación de módulo simple. Por ejemplo, p (bc) = 15 es un divisor de p (abcd) = 210, por lo que bc es un subconjunto de abcd (como lo son los conjuntos abd y abc).
Agregar un nuevo conjunto S a la colección existente de N conjuntos es O (N), suponiendo que la comparación y división de los números grandes lleva más o menos el mismo tiempo, independientemente de N.
Para cada entrada E existente en la colección de conjuntos, detenga si p (S) <p (E) y p (S) divide p (E) exactamente. Si p (S) = p (E), deténgase. Quite E si p (S)> p (E) y p (E) divide p (S) exactamente. Agrega S si llegas al final de la colección. Una matriz de BigNums funcionaría.

@JL: si desea ser mi acosador en el sitio, intente 1) agregar valor 2) con precisión.