使用 Numpy 查找数组中的行组合，以便每列的总和为相同的值

Question

我正在尝试使用numpy来查找矩阵中行的配置，以便对行的列求和将产生相同的值。例如，对于矩阵/数组

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

我想将第一、第二和最后一行作为输出，因为

0,0,0,1
1,0,1,0
0,1,0,0 +
-------
= 1,1,1,1

numpy中是否有任何内置工具可以帮助我获取此内容？

Answer 1

一种解决方案是枚举行的幂集，然后检查每个可能的行子集是否存在求和条件。对于具有大量行的矩阵，这可能非常慢。

使用电源组的标准迭代工具配方：

from itertools import chain, combinations
def powerset(iterable):
xs = list(iterable)
return chain.from_iterable(combinations(xs, n) for n in range(len(xs) + 1))

然后我展示了一个带有一些合成数据的工作示例：

In [79]: data
Out[79]: 
array([[0, 1, 1],
[0, 0, 1],
[1, 0, 1],
[0, 1, 1],
[0, 0, 0],
[0, 1, 0],
[1, 1, 1],
[1, 1, 0],
[1, 1, 1],
[0, 1, 0]], dtype=int32)
In [80]: def is_constant(array):
...:     return (array == array[0]).all()
...: 
In [81]: solution = []
In [82]: for candidate in powerset(range(len(data))):
...:     if candidate and is_constant(data[candidate, :].sum(axis=0)):
...:         solution.append(candidate)
...: 

例如，它显示：

In [83]: solution
Out[83]: 
[(4,),
(6,),
(8,),
(1, 7),
(2, 5),
(2, 9),
(4, 6),
(4, 8),
(6, 8),
(0, 2, 7),
(1, 4, 7),
(1, 6, 7),
(1, 7, 8),
(2, 3, 7),
(2, 4, 5),
(2, 4, 9),
(2, 5, 6),
(2, 5, 8),
(2, 6, 9),
(2, 8, 9),
(4, 6, 8),
(0, 2, 4, 7),
(0, 2, 6, 7),
(0, 2, 7, 8),
(1, 2, 5, 7),
(1, 2, 7, 9),
(1, 4, 6, 7),
(1, 4, 7, 8),
(1, 6, 7, 8),
(2, 3, 4, 7),
(2, 3, 6, 7),
(2, 3, 7, 8),
(2, 4, 5, 6),
(2, 4, 5, 8),
(2, 4, 6, 9),
(2, 4, 8, 9),
(2, 5, 6, 8),
(2, 6, 8, 9),
(0, 2, 4, 6, 7),
(0, 2, 4, 7, 8),
(0, 2, 6, 7, 8),
(1, 2, 4, 5, 7),
(1, 2, 4, 7, 9),
(1, 2, 5, 6, 7),
(1, 2, 5, 7, 8),
(1, 2, 6, 7, 9),
(1, 2, 7, 8, 9),
(1, 4, 6, 7, 8),
(2, 3, 4, 6, 7),
(2, 3, 4, 7, 8),
(2, 3, 6, 7, 8),
(2, 4, 5, 6, 8),
(2, 4, 6, 8, 9),
(0, 2, 4, 6, 7, 8),
(1, 2, 4, 5, 6, 7),
(1, 2, 4, 5, 7, 8),
(1, 2, 4, 6, 7, 9),
(1, 2, 4, 7, 8, 9),
(1, 2, 5, 6, 7, 8),
(1, 2, 6, 7, 8, 9),
(2, 3, 4, 6, 7, 8),
(1, 2, 4, 5, 6, 7, 8),
(1, 2, 4, 6, 7, 8, 9)]

我们可以针对以下几种情况验证解决方案：

In [84]: data[(1, 2, 4, 6, 7, 8, 9), :].sum(axis=0)
Out[84]: array([4, 4, 4])
In [85]: data[(0, 2, 4, 6, 7), :].sum(axis=0)
Out[85]: array([3, 3, 3])

为了将其扩展到更具体的用例，您可以使用itertools.combinations生成仅特定大小的子集，例如正好 2 行或正好 3 行的子集等。

或者，您可以从我示例中给出的结果集中过滤掉不需要的结果(例如一次由一行组成的琐碎解决方案(。

请注意，您可以简化powerset的函数定义(我使用的函数定义实际上只是取自有关 itertools 配方的 Python 文档(。与其传递转换为列表的可迭代对象，不如直接传递一个整数并直接跳过以返回最终的chain.from_iterable结果，然后修改为仅传递len(data)作为我示例中的powerset参数，如下所示：

from itertools import chain, combinations
def powerset(N):
"""Power set of integers {0, ..., N-1}."""
xs = list(range(N))
return chain.from_iterable(combinations(xs, n) for n in range(N + 1))
...
for candidate in powerset(len(data)):
...