Trovare un sottoinsieme che soddisfa una certa condizione

Question

ho più array di numeri (ciascun elemento della matrice può assumere solo un valore di 0 o 1) simili

 
v1: 1; 0; 0; 1; 1; 
v2: 0; 1; 0; 0; 1; 
v3: 1; 1; 0; 1; 0; 
v4: 1; 0; 0; 1; 0; 
v5: 1; 1; 0; 1; 1; 
v6: 1; 1; 0; 1; 1; 

desidero trovare sottoinsiemi tali che, quando gli array vengono sommati, l'array risultante ha singoli elementi che sono multipli di 2. Ad esempio, v1 + v2 + v3 fornisce un array risultante di 2, 2, 0, 2, 2. L'array risultante può avere qualsiasi valore che sia un multiplo di 2.

un altro esempio:

 
v1: 1, 1, 1, 0, 1, 0 
v2: 0, 0, 1, 0, 0, 0 
v3: 1, 0, 0, 0, 0, 0 
v4: 0, 0, 0, 1, 0, 0 
v5: 1, 1, 0, 0, 1, 0 
v6: 0, 0, 1, 1, 0, 0 
v7: 1, 0, 1, 1, 0, 0 

In questo esempio, v1 + v2 + v5 e v3 + v6 + v7 sono risposte appropriate.

Ho una soluzione di forza bruta in mente, ma volevo verificare se esiste un metodo più efficiente. Questo è equivalente al problema della somma dei sottoinsiemi?

Answer 1

Vuoi trovare tutte le soluzioni o una?

Questo può trovare una soluzione (e penso che sia possibile estenderla per trovare tutte le soluzioni).

Rappresenta ogni array come un numero binario.

Quindi v1 diventa 10011, v2 diventa 01001 ecc

Let * denotano bit a bit mod 2 aggiunta.

ad es.

v1*v2*v3 = 00000 

Quindi il nostro obiettivo è trovare array la cui aggiunta di mod 2 è tutti zero. Sia u che v un numero binario. Quindi u * v = 0 iff u = v.

ad es.

(v1*v2)*v3 = 0 
v1*v2 = 11010 = v3. 

anche se u * v = w quindi

u*v*v = w*v, so 
u*0 = w*v, 
u = w*v 

Così possiamo fare una ricerca inversa a partire da 0. Supponiamo che il set finale di array contiene v. Poi v * T = 0, dove T è un numero binario. Abbiamo T = 0 * v. Se T è uno degli array dati, allora abbiamo finito. Altrimenti continuiamo la ricerca a partire da T.

Questo è formalmente descritto di seguito.

Ogni stato è un numero binario.

Sia 0 lo stato iniziale.

I dati array sono un sottoinsieme dello spazio degli stati, dice S.

Il nostro stato obiettivo è alcun elemento a S.

Sia T il sottoinsieme di array richiesto la cui somma è 0.

Ad ogni stato lasciare che le azioni possibili siano * con qualsiasi stato non in T.

Dopo ogni azione inserire la matrice utilizzata in T.

Se S = T in qualsiasi fase non obiettivo, quindi non c'è soluzione.

Ora possiamo eseguire un DFS su questo spazio per trovare una soluzione.