二值矩阵的最小方差

Question

我有一个0和1的矩阵，例如:

X = 
[[1, 1, 0, 0],
[1, 0, 1, 1],
[0, 0, 1, 1],
[1, 1, 1, 1],

在每一行中，只选择一个'1'，其余为0，以便在每一列中获得相同数量的'1'。基本上，得到按列求和后的最小方差。例子:从上面的X，答案是:

Y = 
[[1, 0, 0, 0],
[0, 0, 0, 1],
[0, 0, 1, 0],
[0, 1, 0, 0],

Y中的每一列都有一个'1'。Y从X的第一行选择第一个'1'，从第2行选择索引4中的第二个'1'，....X可以是任意大小

我该怎么做呢?对不起，我的英语不好。

Answer 1

编辑:下面是一个蛮力技术，它可以找到每个"解决方案"。它不适用于非正方形数组，因为OP的问题在如何处理非正方形数组上是模糊的。我想到的寻找随机解的技术只是一个简单的回溯算法在idxs上，如果别人没有想出更好的方法，我明天可能会用到它。

这是一个蛮力解，它取列索引的笛卡尔积，其中每行有一个1:

import itertools
import numpy as np

x = np.array([[1, 1, 0, 0],
[1, 0, 1, 1],
[0, 0, 1, 1],
[1, 1, 1, 1]])

n = x.shape[1]
rows, cols = np.argwhere(x).T
idxs = np.split(cols, np.unique(rows, return_index=True)[1][1:])
col_idxs = [t for t in itertools.product(*idxs) if len(set(t)) == n]
row_idxs = np.arange(n)

显示此特定X的所有解:

for t in col_idxs:
z = np.zeros_like(x)
z[row_idxs, t] = 1
print(f"{z}n")

输出:

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