用具有多个结果的矩阵构建地图

Question

i具有未知的n x m尺寸的输入矩阵，由1s和0s

填充

例如，一个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映射是每列和行最多可以使用一次。

理想的解决方案具有最多的映射 ie。所使用的最多的行和列。它还应该避免详尽的组合或操作，这些组合或操作与较大的矩阵不能很好地扩展(实际上，最大尺寸应为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.

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

Answer 2

让我放手。我建议的算法并不总是提供最佳解决方案，但也许有人可以改进。

1. 您总是可以互换两列或两个行而不会改变问题。此外，通过跟踪更改，您可以随时回到原始问题。

2. 我们将用1S填充主角。通过互换列或行或两者在左上角获取第一个1。现在，第一行和列已固定，我们不再触摸它们了。现在，我们尝试用1填充对角线上的第二个元素，然后修复第二行和列。等等。

3. 如果右下右键为零，我们应该尝试通过使用整个矩阵互换两列或两个行来将1列入其中，但可以保留对角线中现有的1s。(这是一个问题。很容易进行有效检查是否可以提供帮助。但是，可能至少需要两个互换，或者更多。(

4. 我们在对角线上没有再获得1时停止。

因此，虽然算法并不总是最佳的，但也许可以提出额外的规则如何互换列和行，以便尽可能与1s填充对角线。