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

Question

Busco a una estructura de datos abstracta que representa una colección de conjuntos tales que ningún conjunto de la colección es un subconjunto de otro conjunto de 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. Inserción de un elemento que es un superconjunto de cualesquiera otros elementos dará lugar a una colección con el superconjunto añadido y los subconjuntos eliminado.

Suponiendo una ordenación sobre los elementos del conjunto, a continuación, un árbol de prefijo puede ser usado para representar la colección. Esto permite que la condición A que se maneja muy rápidamente (es decir, ya no se lleva a comprobar el estado de lo que sería para insertar el subconjunto), sin embargo el cumplimiento de la condición B lleva tiempo.

Me pregunto si hay una estructura de datos que permite B que deben cumplir rápidamente también.

Answer 1

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

Esto, obviamente, se ejecuta en tiempo O (n) para la búsqueda lineal y tamaño posiblemente O (m) para el tamaño del conjunto de entrada. Por lo tanto O (n * m) tiempo total (número de conjuntos vs. tamaño de cada set).

La optimización más obvia, por supuesto, es que el índice de tamaños establecidos. Entonces sólo probar cada conjunto de entrada en contra de aquellos que son de tamaño igual o más grande. (Un conjunto no puede ser un subconjunto de cualquier conjunto más pequeño, duh!).

La siguiente optimización que viene a la mente es la de crear en el índice de elementos. Así, para cada conjunto de entrada que iba a encontrar la intersección de cada uno de los conjuntos que contienen cada uno de los elementos. En otras palabras, si, para el grupo entrante {a, b, c}, nos encontramos con que el elemento {a} existe en los conjuntos A, B y D, elemento {b} existe en B, E y F, y {c} existe en a, B y Z ... entonces el conjunto de entrada es un subconjunto de B (la intersección de {a, B, D}, {B, e, F} y {a, B, Z}).

Por lo tanto, que suena como (log m * (n)) O complejidad a mí. (Tenemos que realizar búsquedas de hash en cada elemento de cada conjunto de entrada). Las inserciones también deben estar en el mismo orden (insertar el ID del nuevo conjunto en cada uno de los mapas del elemento). (En el análisis de Big-O 2 * O (m log (n)) se reduce a O (m log (n)), por supuesto).

Answer 2

Una idea trivial, que trabajará en O (K), donde K se agrega tamaño de elemento.

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

ambos A y B son O (K).

Answer 3

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

Usted podría terminar con unos números muy grandes, supongo, pero funciona en la teoría.

Por ejemplo:

Si [a b c d] -> [2 3 5 7], p (abc) = 30, p (abd) = 42, p (bc) = 15, p (abcd) = 210

Answer 4

Lo que un sitio dorky! Ahora he registrado, por lo que puede que en su momento será capaz de comentar 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: la búsqueda de los factores de una   número arbitrario de hecho es NP completo, pero no es relevante aquí. los   cuestión 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,   así bc es un subconjunto de abcd (como son 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 E existente en la colección de conjuntos, detenga si p (S)   

p (E) y P (E) divide P (S) exactamente. Añadir S si se llega a la final de la colección. Una matriz   de bignums funcionarían.

---

@JL:. Si desea ser mi acosador en el lugar por favor, procure 1) agregar valor 2) con precisión