algorithm - 在矩阵中查找值的组合

Question

我正在解决一个离散数学问题，如果可能(不是 2^n)，我需要找到一个最优解。

我有一个矩阵

假设

.. 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

是否可以在不检查每个组合的情况下找到给出 5 [1] : 1 1 1 1 1 的所有行组合？

我想过在另一个有更多行的矩阵中对这个矩阵进行排序，其中第一行将是第一个矩阵中第一列为 1 的行 例子: ..0 1 2 3 4
..0 1 1 0 0 0 - 这有第 1 [1] 列
..1 1 1 1 0 0 - 这有第 1 [1] 列
..2 1 1 0 0 0 - 这有第 2 [1] 列
..3 1 1 1 0 0 - 这有第 2 [1] 列
..4 0 1 1 1 1 - 这有第 2 列 [1]
..5 1 1 1 0 0 - 这有第 3 列 [1]
..6 0 1 1 1 1 - 这有第 3 列 [1]
..7 0 0 0 1 1 - 这有第 4 列 [1]
..8 0 1 1 1 1 - 这有第 4 列 [1]
..9 0 0 0 1 1 - 这有第 5 列 [1]
10 0 1 1 1 1 - 这有第 5 列 [1]

现在将给出 row 的所有行与 5 [1] 合并

给出 5 [1] 的行的组合表示:
看0和1是假还是真
观看第一个矩阵:
第 0 行:1 1 0 0 0 + 第 3 行 0 1 1 1 1
“+”在这种情况下表示“或”:
所以:第 0 行 + 第 3 行给出了五个 ONES 的组合
还有很多组合
有什么想法吗？

Answer 1

我会为每一列创建一组行，该列中有 1 的行。在我们的例子中，我们将有 5 组 5 列:

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

创建一个在所有列中产生 1 的组合会导致从每个集合中简单地选择一个项目。创建所有组合就像遍历所有集合并忽略已找到的组合一样简单。