¿Cómo encontrar los elementos no idénticos de múltiples vectores?

Question

Dado varios vectores/conjuntos, cada uno de los cuales contiene números enteros múltiples que son diferentes dentro de un vector. Ahora quiero comprobar, si existe un conjunto que se compone de extraer solo un elemento de cada vectores/conjuntos dados, en el mismo tiempo los números extraídos son no idénticos entre sí.

Por ejemplo, dada fija a, b, c, d como:

a <- (1,3,5); 
b <- (3,6,8); 
c <- (2,3,4); 
d <- (2,4,6) 

puedo averiguar conjuntos como (1, 8, 4, 6) o (3, 6, 2, 4) ..... en realidad, solo necesito encontrar uno de esos conjuntos para probar la existencia.

aplicando la búsqueda de fuerza brutal, puede haber combinaciones máximas m^k para verificar, donde m es el tamaño de conjuntos dados, k es el número de conjuntos dados.

¿Hay alguna manera más inteligente? ¡Gracias!

Answer 1

Puede reformular el problema como un juego en un grafo bipartito:

• el nodo del lado izquierdo son sus conjuntos,
• el nodo del lado derecho son el número entero que aparece en los conjuntos.

Hay un borde entre un nodo "conjunto" y un nodo "entero" si el conjunto contiene el número entero dado. Luego, intenta encontrar una coincidencia en este gráfico bipartito: cada conjunto se asociará a un entero y ningún número entero se usará dos veces. El tiempo de ejecución de un algoritmo simple para encontrar tal coincidencia es O (| V || E |), aquí | V | es más pequeño que (m + 1) k y | E | es igual a mk. Entonces tienes una solución en O (m^2 k^2). Ver: Matching in bipartite graphs.

algoritmo de asociación bipartita:

El algoritmo funciona en los gráficos orientados. Al principio, todos los bordes están orientados de izquierda a derecha. Se combinarán dos nodos si el borde entre ellos está orientado de derecha a izquierda, por lo que al principio, la coincidencia está vacía. El objetivo del algoritmo es encontrar "rutas de aumento" (o rutas alternas), es decir, rutas que aumenten el tamaño de la coincidencia.

Una ruta de aumento es una ruta en el gráfico dirigido que comienza desde un nodo izquierdo sin igual y termina en un nodo derecho no coincidente. Una vez que tienes un camino de aumento, solo tienes que voltear todos los bordes a lo largo de la ruta para incrementar el tamaño de la coincidencia. (El tamaño de la coincidencia aumentará porque tiene un borde más que no pertenece a la coincidencia. Esto se denomina una ruta alternativa porque la ruta alterna entre los bordes que no pertenecen a la coincidencia, de izquierda a derecha y los bordes que pertenecen a la coincidencia, derecha a izquierda)

Aquí es cómo encontrar una trayectoria de aumento:.

1. todos los nodos se marcan como no visitado,
2. a escoger un nodo no visitado e incomparable izquierda,
3. haces una la primera búsqueda de profundidad hasta que encuentre un nodo derecho sin igual (luego tiene una ruta de aumento). Si no puede encontrar un nodo derecho sin igual, vaya a 2.

Si no puede encontrar un camino de aumento, entonces la coincidencia es óptima.

Encontrar un camino de aumento es de complejidad O (| E |), y lo hace como mínimo (k, m) veces, ya que el tamaño de la mejor coincidencia está limitado por k y m. Entonces, para su problema, la complejidad será O (mk min (m, k)).

También puede ver this reference, sección 1., para obtener una explicación más completa con las pruebas.