python - 从具有多个结果的矩阵构建 map

Question

我有一个未知的 n x m 维度的输入矩阵，由 1 和 0 填充

例如，一个 5x4 矩阵:

A = array(
  [[1, 0, 0, 0],
   [1, 0, 0, 0],
   [0, 1, 1, 0],
   [0, 1, 1, 0],
   [1, 0, 1, 1]])

目标

我需要在尽可能多的列和行之间创建一个 1 : 1 映射，该位置的元素为 1。

我所说的 1 : 1 map 的意思是每列和每行最多只能使用一次。

理想的解决方案具有尽可能多的映射，即。使用最多的行和列。它还应避免无法很好地扩展较大矩阵的详尽组合或操作(实际上，最大尺寸应为 100x100，但没有声明限制，因此它们可以更高)

这是上述的可能结果

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

更多示例:

input:
0 1 1
0 1 0
0 1 1

output (one of several possible ones):
0 0 1
0 1 0
0 0 0 

另一个(这表明可能出现的一个问题)

input:
0 1 1 1
0 1 0 0
1 1 0 0

a good output (again, one of several):
0 0 1 0
0 1 0 0
1 0 0 0

a bad output (still valid, but has fewer mappings)
0 1 0 0
0 0 0 0
1 0 0 0

为了更好地展示它们如何成为多个输出

input: 
0 1 1
1 1 0

one possible output:
0 1 0
1 0 0

a second possible output:
0 0 1
0 1 0

a third possible output
0 0 1
1 0 0

我做了什么？

我现在有一种非常愚蠢的处理方式，根本不能保证有效。基本上我只是用单位矩阵构建一个过滤矩阵(因为它是完美的映射，每一行和每一列都使用一次)然后我随机交换它的列(n 次)并用它过滤原始矩阵，记录过滤器具有最佳结果的矩阵。

My [non] solution:

import random
import numpy as np

# this is a starting matrix with random values
A = np.array(
  [[1, 0, 0, 0],
   [1, 0, 0, 0],
   [0, 1, 1, 0],
   [0, 1, 1, 0],
   [1, 0, 1, 1]])

# add dummy row to make it square
new_col = np.zeros([5,1]) + 1
A = np.append(A, new_col, axis=1)

# make an identity matrix (the perfect map)
imatrix = np.diag([1]*5)

# randomly swap columns on the identity matrix until they match. 
n = 1000

# this will hold the map that works the best
best_map_so_far = np.zeros([1,1])

for i in range(n):
    a, b = random.sample(range(5), 2)
    t = imatrix[:,a].copy()
    imatrix[:,a] = imatrix[:,b]
    imatrix[:,b] = t

    # is this map better than the previous best?
    if sum(sum(imatrix * A)) > sum(sum(best_map_so_far)):
        best_map_so_far = imatrix

    # could it be? a perfect map??
    if sum(sum(imatrix * A)) == A.shape[0]:
        break
    # jk.

# did we still fail
if sum(sum(imatrix * A)) != 5:
    print('haha')

# drop the dummy row
output = imatrix * A
output[:,:-1]

#... wow. it actually kind of works.

Answer 1

这个怎么样？

let S be the solution vector, as wide as A, containing row numbers.
let Z be a vector containing the number of zeros in each column.

for each row:
    select the cells which contain 1 in A and no value in S.
    select from those cells those with the highest score in Z.
    select from those cells the first (or a random) cell.
    store the row number in the column of S corresponding to the cell.

这是否为您提供了充分的解决方案？如果是这样，它应该比您拥有的效率高得多。