Finding combination of values in matrix

Question

I am solving a problem from discrete mathematics and i need to find an optimal solution if it possible(not 2^n).

I got a matrix

Let's say

.. 0 1 2 3 4
0 1 1 0 0 0
1 0 0 0 1 1
2 1 1 1 0 0
3 0 1 1 1 1

Is it possible to find all the combinations of rows that gives 5 [1] : 1 1 1 1 1 without checking every single combination ?

I thought about sorting this matrix in another matrix with more rows where the first one rows will be the rows from the first matrix that got 1 for the first column Example: ..0 1 2 3 4
..0 1 1 0 0 0 -This has got column 1 [1]
..1 1 1 1 0 0 -This has got column 1 [1]
..2 1 1 0 0 0 -This has got column 2 [1]
..3 1 1 1 0 0 -This has got column 2 [1]
..4 0 1 1 1 1 -This has got column 2 [1]
..5 1 1 1 0 0 -This has got column 3 [1]
..6 0 1 1 1 1 -This has got column 3 [1]
..7 0 0 0 1 1 -This has got column 4 [1]
..8 0 1 1 1 1 -This has got column 4 [1]
..9 0 0 0 1 1 -This has got column 5 [1]
10 0 1 1 1 1 -This has got column 5 [1]

And now to combine all the rows that gives row with 5 [1]

Combinations of rows that gives 5 [1] means:
Look at 0 and 1 as false and true
Watching at the first matrix:
Row 0: 1 1 0 0 0 + Row 3 0 1 1 1 1
"+" means "OR" in this case:
So : Row 0 + Row 3 gives a combination of five ONES
And there are a plenty of comibnations
Any ideas ?

Please define "give" in "combinations of rows that gives 5 [1]". — Eldritch Conundrum
– Eldritch Conundrum, Commented Dec 26, 2013 at 13:00
It's worth noting that there are 2^n-1 combinations in the worst case, so, if you want to print all of them, no algorithm can do better than that. — Bernhard Barker
– Bernhard Barker, Commented Dec 26, 2013 at 14:12

Dialecticus · Accepted Answer · 2013-12-26 13:35:27Z

I would create a set of rows for each column, rows that have 1 in that column. In our case we would have 5 sets for 5 columns:

0: {0, 2}
1: {0, 2, 3}
2: {2, 3}
3: {1, 3}
4: {1, 3}

Creating one combination that produces 1s in all column results in simply picking one item from every set. Creating all combinations is as simple as looping through all sets, and ignoring already found combinations.

Collectives™ on Stack Overflow

Finding combination of values in matrix

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related