Click here to Skip to main content
15,389,177 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
I have a 2D array with ones and zeros, for example:

1 0 0 0
0 1 0 0
1 0 1 0
1 0 0 1

I need to find if there is a group of columns (or a single column) that have a row sum equal 1. For the above array the answer is YES because:

1 + 0 = 1
0 + 1 = 1
1 + 0 = 1
1 + 0 = 1

Edit:
This solution will work for much bigger arrays (for example 900x600). That's why I'm trying to avoid a brute force solution.

What I have tried:

Looking for a solution online and trying to find to come up with a better solution than brute forcing it.
Posted
Updated 10-Mar-22 8:08am
v2
Comments
PIEBALDconsult 10-Mar-22 11:53am
   
More detail is required.
Member 15561967 10-Mar-22 12:00pm
   
What other detail do you need? I'd be happy to add it to the original post.
jeron1 10-Mar-22 11:56am
   
I would initially 'brute force' it, then try and optimize only if necessary. If you have specific questions during that process, feel free to ask them here.
Member 15561967 10-Mar-22 13:20pm
   
Brute force will be very slow for a bigger array. That's what I'm trying to avoid.
Rick York 10-Mar-22 12:16pm
   
Brute force is the appropriate thing to try in my opinion. There appear to be only eight possibilities so it's really not so bad. That is, four columns combined two at a time.
Member 15561967 10-Mar-22 13:22pm
   
Brute force will be very slow for a bigger array. That's what I'm trying to avoid. I've updated the question.

1 solution

Aha, That is a special case of a more general optimisation job I've spent many years on; I ended up with a very nice approach that is the opposite of brute force, and provides all solutions in one go.

Applied on your matrix situation, I'd like to describe it using boolean logic, i.e. all variables will have values 0 or 1, and the operators are AND (written as .), OR (written as +), and invert (written as /). Here we go:

call your columns A, B, C, D, ...
introduce variables a, b, c, d, indicating whether the corresponding column is or isn't used in the solution.

Now start building a, possibly huge, boolean expression TARGET, using the following pseudocode:
pseudo
TARGET=1
foreach row {
    expr = some expression describing the row (explained below)
    TARGET = TARGET . expr
}
now reduce the TARGET expression using three facts:
step 1 = explode: x.(y+z) => x.y + x.z
step 2 = discard zeroes: x./x => 0
step 3 = power reduction: x.x => x

you can merge these steps (i.e. perform steps 2 and 3 while executing step 1), for clarity I will show them separately in the above order

what remains is the list of all solutions, pick any one of the terms and make it 1.
Depending on the matrix content, you will get zero, one or several solutions. 


Applied to your example:
a b c d
1 0 0 0
0 1 0 0
1 0 1 0
1 0 0 1


TARGET= 1        // for starters
.a               // row 1 says you need a
.b               // row 2 says you need b
.(a./c + /a.c)   // row 3 says you need either a or c but not both
.(a./d + /a.d)   // similar for row 4


exploded gives four terms as there are two groups of 2 terms in the expression:
TARGET=a.b.a./c.a./d + a.b./a.c.a./d + a.b.a./c./a.d + a.b./a.c./a.d

zero discarding will drop the last three products as they all contain a./a
power reduction of the remaining product yields:

TARGET=a.b./c./d


which means you must include A and B and must not include C and D.

For more complex problems, a typical final expression could be:

TARGET = a.b./c./d + a./b./c.d.e + /a.b.c./d.e


remarks:

1. when processing (inside the foreach loop) a row that holds N ones, you need N products; each product would have one positive column and N-1 inverted columns. So if there were a fifth row with "1 0 1 1" that would contribute (a./c./d + /a.c./d + /a./c.d)

2. when the final TARGET would hold S products, that indicates there are S solutions; any combination of variables that makes one product true or one, is a solution (no matter what the other products contribute).

3. when a product in the final TARGET does not hold all column variables, that means the missing columns are don't care, which in your application means those columns contain all zeroes.

4. if all-zero rows are present, you'll get TARGET = 0, so no solution.


So far the logic or mathematics. How you code this I'll leave up to you.
   
v4
Comments
Member 15561967 10-Mar-22 16:25pm
   
Thank you very much! I read it all and everything is clear. Unfortunately I will have to code it tommorrow, but this is what I was looking for.
Luc Pattyn 10-Mar-22 16:47pm
   
Here is one idea for implementation with C# in mind, any language would do:
- you could define a Term class that basically is an array for the states of ALL the variables a,b,c,d (i.e. positive, inverse, or absent) plus something special for always true and always false. I would actually use a List (a stretchable array), I seldom use arrays any more.
- then implement AND operation for Term (with simplification steps 2 and 3 built in)
- then implement a Sum class which just holds zero or more Term objects (again a List) in an OR relationship and knows how to multiply two Sums (with immediate explode).
- define TARGET as a Sum initialized to 1
- then implement the "foreach row" loop performing Sum.Sum all the time.

A whole day should be a luxury...


This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900