CODEWITHSUNDEEP
algorithmmatrix
Martin Djonov
Martin Djonov

Reputation: 43

Finding combination of values in matrix

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 ?

Upvotes: 0

Views: 241

Answers (1)

Dialecticus
Dialecticus

Reputation: 16761

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.

Upvotes: 2

Related Questions