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

Question

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

Esto significa que en el inserto se cumplen las siguientes condiciones:

A. Inserción de 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.

Suponiendo un pedido de 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.

Answer 1

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

Esto obviamente se ejecuta en O (n) tiempo para la búsqueda lineal y posiblemente 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 suena a O (m * log (n)) complejidad. (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).

Answer 2

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

• mantener los juegos en cualquier forma u desea
• mapa torreón de set_id -> set_size
• mapa torreón del objeto -> set_id

tanto A como B son O (K).

Answer 3

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

Podría 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

Answer 4

¡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 adecuada me parece haber adquirido un explicador: se ha perdido trozos, sin embargo, y su comentario debe decir lo siguiente:

---

@Stephen C: encontrar los factores de un número arbitrario es de hecho NP completo, pero no es 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).

Adición de un nuevo conjunto S a la colección existente de N conjuntos es O (N), suponiendo que la comparación y la división de los grandes números toma aproximadamente al mismo tiempo, independientemente de N.

Para cada entrada existente E en la colección de conjuntos, detener si p (S) < p (E) yp (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 lugar por favor, procure 1) agregar valor 2) con precisión.