Algoritmo para encontrar subconjuntos comunes

Question

tengo N número de conjuntos S _i de números, cada uno de un tamaño diferente. Deje m, m, ... m _n ser los tamaños de los respectivos conjuntos (m _i = | S _i |), y M ser el tamaño del conjunto más grande. Tengo que encontrar subconjuntos comunes que tengan al menos dos números en ellos. Ejemplo:

Set Items 
1 10,80,22 
2 72, 10, 80, 26,50 
3 80, 
4 10, 22 
5 22, 72, 10, 80, 26,50 

Así, el resultado será como el

Items    Found in sets 
10, 22    1, 4 
10, 80    1, 2, 5 
10, 80, 22   1, 5 
10, 72, 80, 26, 50 2, 5 

Entonces, ¿cómo automatizar este problema y lo que es la complejidad esperada para la solución respectiva? Necesito que sea lo más rápido posible.

Answer 1

Tengo algunos consejos. Debería ordenar todos los elementos en conjuntos, cuando realiza un ciclo en bucle para contar un número en ese conjunto. Debería agregar la condición para verificar que un número es mayor que el valor de búsqueda y usar el salto; para el final del ciclo

Answer 2

Usted puede hacer esto -

1. Crear una tabla hash & inserto como claves de cada uno de sus artículos & valores como los conjuntos que pertenecen. Eg: 10:[0,1,3,4] 80:[0,1,2,4] 22:[0,3,4] 72:[1,4] 26:[1,4] 50:[1,4]

2. Después de esto para cada 2 elementos en la tabla hash, encuentre la intersección de los valores de las teclas. Aquí la intersección de (10, 80) da [0,3,4]. Haga esto por (10,22) (10,72) ... Tiene su resultado.

3. Complejidad - Para insertar artículos M en la tabla de Hash - O (M) Buscar cada tecla en la tabla hash - O (1) operación Intersección de de valor de clave - O (m^2) [Esto podría optimizado]

En general, diría que esto es O (m^2) algo. Pero si el tamaño de "Elementos" no es grande en cada "Conjunto", entonces no notaría mucho golpe de rendimiento.

Answer 3

Una solución que se me ocurre:

utiliza una tabla hash, generar toda la combinación de "un par de números" de los números en que "fila", que es un tiempo O (M * M).

A continuación, utilícelos como las teclas de acceso directo, asignando al índice de matriz principal.

For each row of those N elements, 
    do the step above... and if the hash already maps to a number, then it is a match, 
    then return the pair, or else just put those in the hash 

es O (N * M * M)

actualización: si, como se dice en el comentario, que M puede ser como máximo de 15, entonces O (N * M M *) es realmente lo mismo que O (N).

---

Si su pregunta inicial es encontrar todos los pares, a continuación,

For each row of those N elements, 
    do the step first mentioned... and if the hash already maps to a number, 
    then it is a match and just print out the pair if this pair is not printed yet 
    and in any event, put the mapping into the hash 

to tell whether a pair has been printed, created another hash, such as 
    printed_or_not[i,j] = true or false, 
    and make sure to check printed_or_not[i,j] or printed_or_not[j, i] 
    because not need to print again if just different order 

Answer 4

Se le pide hacer el cruce por pares de todo el conjunto y recoger todos los resultados que son de tamaño> = 2

Hay pares O (N^2). Hacer la intersección es O (M) para cada uno. Reúna todos los resultados, ordénelos por los contenidos establecidos para resolver los duplicados. N^2 Log N^2 (el peor caso es que la intersección es diferente para cada par, por lo que puede haber O (N^2) conjuntos de resultados)

Así que creo que la complejidad es O ((N^2 + N log N) * M)

Pero hay bastante posible un error en alguna parte.

Paul

Answer 5

Dado que la pregunta original pide hacer una discusión lo más rápido posible, así es como se puede hacer corto.

Primero, discuta si la salida es exponencial a su entrada. Supongamos que tiene 2 elementos y N conjuntos. Supongamos que cada elemento pertenece a cada conjunto; requerirá N líneas como su entrada. Entonces, ¿cuántas líneas debe imprimir?

creo que va a imprimir 2 ^N -N-1 líneas, como los siguientes:

1,2  1,2 
1,2  1,3 
..... 
1,2  1,N 
1,2  2,1 
..... 
1,2  1,2,3 
..... 
1,2  1,2,3,...N 

Puesto que usted va a gastar el tiempo de impresión O (2 ^N), puede elegir cualquiera de las sugerencias en esta página para calcular esta información; de todos modos, ha sido atrapado por un exponente.

Este argumento haría su discusión muy rápida.