python - 在至少 'x' 列中包含非零值的最大行集

Question

有点复杂但简单的矩阵运算。我想找到并最大化行数，这样至少有 x 列，其中受这些行约束的矩阵全部为 1。

行本身不需要连续，列也不需要。矩阵假定所有行至少有 x 个行，因此，我不会删除任何没有最小 x 的行。

我的初始方法如下:占据第一行。查找其中包含 1 的前“x”列。然后对于这些列，检查有多少行也有 1。跟踪我找到了多少行。从每一行开始这样做。

但是，这是行不通的，因为即使对于第一行，我也需要考虑所有不同的列组合，这些组合仍然给我最小的 x 列，其中包含 1，而不仅仅是前 x 列。

为此，计算时间很快就会爆炸。有解决这个问题的有效方法吗？

我正在尝试用 python 来做。

考虑以下示例，x = 2。

这没有解，因为第 1、3、5 行最初都被消除了。然后，对于第 2 行和第 4 行，没有 3 列在两行中都有一个。

但是在这里，第 2 行和第 4 行至少有 3 列全为 1。所以这有一个解决方案，最大行数是2。

Answer 1

您所描述的似乎是对关联规则学习问题的重新表述，例如可以使用 Apriori 算法解决该问题。

这是快速制作的示例，展示了该算法的基础知识。它可能需要一些改进并且不确定是否没有错误。

它也没有要求它必须找到所有不同的列组合，以提供最少的 'x' 行。它仅使用“x”来更快地过滤所有解决方案，并最终返回一个解决方案，该解决方案是具有至少“x”行的列数最多的解决方案。

from operator import itemgetter, or_
from itertools import combinations, starmap
from collections import Counter
from math import factorial


class Apriori:

    def __init__(self, input, x):
        self.input = input
        self.cols = len(input[0])
        self.rows = len(input)
        self.x = x

    def _get_freq_combs(self, comb):
        return sum(map(lambda row:
                       sum([bool(e) for i, e in enumerate(row)
                            if i in comb]) // len(comb), self.input))

    def _make_new_combs(self, combs, comb_size):
        candidates = Counter(map(frozenset,
                                 starmap(or_, combinations(combs, 2))))
        possible_candidate_freq = factorial(comb_size) // factorial(2) \
            // factorial(comb_size - 2)
        for c, f in candidates.items():
            if f == possible_candidate_freq:
                yield c

    def solve(self):
        """Returns a list of sets with the most common items, at least x."""
        freq = [self._get_freq_combs([i]) for i in range(self.cols)]

        most_freq = [{ind} for ind in range(self.cols) if freq[ind] >= x]
        comb_size = 2
        while most_freq:
            old_freq = most_freq
            most_freq = [c for c in self._make_new_combs(most_freq, comb_size)
                         if self._get_freq_combs(c) >= x]
            comb_size += 1
        return old_freq


if __name__ == '__main__':
    input = [[1, 0, 1, 0],
             [0, 1, 1, 0],
             [0, 1, 1, 1],
             [0, 0, 0, 1]]
    x = 2
    apriori = Apriori(input, x)
    print(apriori.solve())