我有一个未知的 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.
最佳答案
这个怎么样?
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.
这是否为您提供了充分的解决方案?如果是这样,它应该比您拥有的效率高得多。
关于python - 从具有多个结果的矩阵构建 map ,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44732678/