Znalezienie podzbiór, który spełnia pewne warunki

Question

Mam kilka tablic liczb (każdy element tablicy może tylko przyjmować wartość 0 lub 1) jak ten

 
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; 

pragnę znaleźć podzbiory takie, że gdy tablice są zsumowane, wynikowa tablica ma pojedyncze elementy, które są wielokrotnościami 2. Na przykład, v1 + v2 + v3 daje wynikową tablicę 2, 2, 0, 2, 2. Wynikowa tablica może mieć dowolną wartość wielokrotnością 2.

Innym przykładem

 
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 

W tym przykładzie odpowiednimi odpowiedziami są v1 + v2 + v5 i v3 + v6 + v7.

Mam na myśli rozwiązanie typu "brute force", ale chciałem sprawdzić, czy istnieje skuteczniejsza metoda. Czy jest to równoważne z problemem sumy podzbiorów?

Answer 1

Chcesz znaleźć wszystkie rozwiązania?

To może znaleźć jedno rozwiązanie (i myślę, że może być możliwe rozszerzenie go w celu znalezienia wszystkich rozwiązań).

Reprezentować każdą tablicę jako liczbę binarną.

Więc v1 staje 10011, 01001 itd v2 staje

Let * oznaczają bitowe mod 2 dodawania.

np.

v1*v2*v3 = 00000 

Naszym celem jest znalezienie tablic, których dodatek do mod 2 jest zerowy. Niech u i v będzie dowolnym numerem binarnym. Następnie u * v = 0 iff u = v.

np.

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

Także jeśli u * v = w ówczesnej

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

więc możemy zrobić do tyłu zaczynając od 0. Załóżmy, że ostateczny zestaw tablic zawiera v. Następnie v * T = 0, gdzie T to pewna liczba binarna. Mamy T = 0 * v. Jeśli T jest jedną z podanych tablic, to skończymy. W przeciwnym razie kontynuujemy wyszukiwanie zaczynając od T.

Zostało to formalnie opisane poniżej.

Każdy stan jest liczbą binarną.

Niech 0 będzie stanem początkowym.

podanej macierzy są niektóre podzbiór przestrzeni stanów, powiedzmy S.

Naszym celem jest stan dowolny element w S.

Niech T będzie wymagana podzbiorem tablic, których suma wynosi 0.

Dla każdego stanu pozwól, aby możliwe działania były * z dowolnym stanem innym niż T.

Po każdej akcji wstaw tablicę używaną w T.

Jeśli S = T na dowolnym etapie bez bramki, to nie ma rozwiązania.

Teraz możemy uruchomić DFS w tym miejscu, aby znaleźć rozwiązanie.