Finding a subset which satisfies a certain condition

Question

I have several arrays of numbers (each element of the array can only take a value of 0 or 1) like this

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; 

I wish to find subsets such that, when the arrays are summed, the resulting array has individual elements which are multiples of 2. For example, v1+v2+v3 gives a resulting array of 2, 2, 0, 2, 2. The resulting array can have any value that is a multiple of 2.

Another example:

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 this example, v1+v2+v5 and v3+v6+v7 are suitable answers.

I have a brute force solution in mind, but I wanted to check if there is a more efficient method. Is this equivalent to the subset sum problem?

Bis

Can you elaborate: 1.) How long are the sets 2.) Do you need the result sum array? – Vaudeville

Number of elements in each array and number of such arrays are unknown at the start of the program. I don't actually need the sum array. Just the numbers of the arrays. So I need 1, 2, 5 if v1+v2+v5 is the result. – Bis

@Banthar wow.. Gaussian elimination does seem like the right thing to do. I just to need find all possible solutions for Vx=0 where V is the matrix with all of my arrays. I think x will give me the corresponding row numbers. – Bis

As to gauss-Jordan: keep in mind x is contrained to being 0/1 in each dimension; and you seek "=0 mod 2", not "=0", again, in each dimension (which isn't the same as looking at this as "=0 mod2" for any norm applied to Vx, say. – Geodetic

@Neo, did Gaussian elimination work for you? If so, can you post that as the answer and accept it? – Shutter

I did not actually follow through with the solution because I had some other stuff to work on.. Like @Geodetic mentioned, the operation required was 0 mod 2, and I also had this nagging doubt about how many solutions will be returned by the Gauss-Jordan method.. If I ever get myself to work on this again, I will definitely post what I did. – Bis

Answer 1

Do you want to find all solutions or one?

This can find one solution (and I think it may be possible to extend it to find all solutions).

Represent each array as a binary number.

So v1 becomes 10011, v2 becomes 01001 etc.

Let * denote bitwise mod 2 addition.

e.g.

v1*v2*v3 = 00000

So our objective is to find arrays whose mod 2 addition is all zeroes. Let u and v be any binary number. Then u*v = 0 iff u = v.

e.g.

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

Also if u*v = w then

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

So we can do a reverse search starting from 0. Suppose the final set of arrays contains v. Then v*T = 0, where T is some binary number. We have T = 0*v. If T is one of the given arrays then we are done. Otherwise we continue the search starting from T.

This is formally described below.

Each state is a binary number.

Let 0 be the initial state.

The given arrays are some subset of the state space, say S.

Our goal state is any element in S.

Let T be the required subset of arrays whose sum is 0.

At each state let the possible actions be * with any state not in T.

After each action put the array used in T.

If S = T at any non goal stage, then there is no solution.

Now we can run a DFS on this space to find a solution.

Agranulocytosis