Come trovare gli elementi non identici da più vettori?

Question

Dati diversi vettori/insiemi, ognuno dei quali contiene più numeri interi che sono diversi all'interno di un vettore. Ora voglio controllare, se esiste un set che è composto estraendo da ogni dato vettori/set, nello stesso tempo i numeri estratti sono non identici l'uno dall'altro.

Ad esempio, dato imposta a, b, c, d come:

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

posso scoprire insiemi come (1, 8, 4, 6) o (3, 6, 2, 4) ..... in realtà, ho solo bisogno di trovare uno di questi set per provare l'esistenza.

applicando la ricerca di forza brutale, ci possono essere le combinazioni m^k per il controllo massimo, dove m è la dimensione di gruppi dati, k è il numero di set dati.

Esistono modi più intelligenti? Grazie!

Answer 1

È possibile riformula il problema come corrispondente in un grafo bipartito:

• il nodo del lato sinistro sono il vostro set,
• il nodo del lato destro sono il numero intero che appare nei set.

C'è uno spigolo tra un nodo "set" e un nodo "intero" se il set contiene il numero intero specificato. Quindi, stai cercando di trovare una corrispondenza in questo grafico bipartito: ogni serie sarà associata a un intero e nessun numero intero sarà usato due volte. Il tempo di esecuzione di un semplice algoritmo per trovare tale corrispondenza è O (| V || E |), qui | V | è più piccolo di (m + 1) k e | E | è uguale a mk. Quindi hai una soluzione in O (m^2 k^2). Vedi: Matching in bipartite graphs.

Algoritmo per corrispondenza bipartito:

L'algoritmo funziona su grafi orientati. All'inizio, tutti i bordi sono orientati da sinistra a destra. Due nodi saranno abbinati se il bordo tra loro è orientato da destra a sinistra, quindi all'inizio la corrispondenza è vuota. L'obiettivo dell'algoritmo è trovare "percorsi incrementanti" (o percorsi alternativi), cioè percorsi che aumentano le dimensioni della corrispondenza.

Un percorso di incremento è un percorso nel grafico diretto che inizia da un nodo sinistro non corrispondente e termina in corrispondenza di un nodo destro senza corrispondenza. Una volta che hai un percorso che aumenta, devi solo capovolgere tutti i bordi lungo il percorso per aumentare la dimensione della corrispondenza. (La dimensione della corrispondenza verrà aumentata perché hai un altro margine che non appartiene alla corrispondenza. Si chiama un percorso alternato perché il percorso si alterna tra i bordi che non appartengono alla corrispondenza, da sinistra a destra, e i bordi che appartengono alla corrispondenza, da destra a sinistra)

Ecco come trovare un percorso che aumenta:.

1. tutti i nodi sono contrassegnati come non visitati,
2. si sceglie un nodo non visitato e senza eguali sinistra,
3. si fa un profondità prima cerca fino a trovare un nodo destro ineguagliato (quindi hai un percorso che aumenta). Se non riesci a trovare un nodo destro ineguagliato, vai al 2.

Se non riesci a trovare un percorso di conversione, la corrispondenza è ottimale.

Trovare un percorso aumentante è di complessità O (| E |), e lo fate al massimo min (k, m) volte, poiché la dimensione della migliore corrispondenza è limitata da k ed m. Quindi per il tuo problema, la complessità sarà O (mk min (m, k)).

È anche possibile vedere this reference, sezione 1., per una spiegazione più completa con le prove.