Python:如何在大于 M 个公共(public)列中找到大于 N 行且单元格非零

Question

我有 n x m 矩阵，我想以编程方式在超过 M 个公共(public)列中找到包含非零单元格的 N 行或更多行。

例如。这是矩阵:

matrix([[ 0.,  0.,  1.,  1.,  1.,  0.,  1.,  0.],
        [ 1.,  0.,  1.,  0.,  1.,  1.,  0.,  1.],
        [ 1.,  0.,  0.,  0.,  0.,  1.,  0.,  0.],
        [ 0.,  0.,  0.,  0.,  1.,  0.,  1.,  0.],
        [ 0.,  1.,  0.,  1.,  1.,  0.,  1.,  0.],
        [ 0.,  1.,  0.,  1.,  0.,  0.,  0.,  0.]])

我正在寻找 2 个或更多行，其中包含 2 个或更多公共(public)列中的非零单元格。有几种可能的结果，其中一种是:

row1: [ 1.,  0.,  1.,  0.,  1.,  1.,  0.,  1.],
row2: [ 1.,  0.,  0.,  0.,  0.,  1.,  0.,  0.],
      col1                     col5

是否可以找到解决此任务的所有行组合？

Answer 1

from pprint import pprint
from itertools import combinations

def solve(lst, m):

    col, n = {}, len(lst)
    for i, x in enumerate(lst):
        col[i] = [j for j, y in enumerate(x) if y]

    for s in xrange(n, m-1, -1):
        for c in combinations(xrange(n), s):
            values  = set(col[c[0]]).intersection(*(col[k] for k in c[1:]))
            if len(values) >= m:
                yield [lst[k] for k in c]

for x in solve(matrix, 2):
    pprint(x)

输出:

[[0, 0, 1, 1, 1, 0, 1, 0],
 [0, 0, 0, 0, 1, 0, 1, 0],
 [0, 1, 0, 1, 1, 0, 1, 0]]
[[0, 0, 1, 1, 1, 0, 1, 0], [1, 0, 1, 0, 1, 1, 0, 1]]
[[0, 0, 1, 1, 1, 0, 1, 0], [0, 0, 0, 0, 1, 0, 1, 0]]
[[0, 0, 1, 1, 1, 0, 1, 0], [0, 1, 0, 1, 1, 0, 1, 0]]
[[1, 0, 1, 0, 1, 1, 0, 1], [1, 0, 0, 0, 0, 1, 0, 0]]
[[0, 0, 0, 0, 1, 0, 1, 0], [0, 1, 0, 1, 1, 0, 1, 0]]
[[0, 1, 0, 1, 1, 0, 1, 0], [0, 1, 0, 1, 0, 0, 0, 0]]