最小化合并行的垂直和的算法

Question

我遇到了一个问题，我正在尝试为其寻找算法。如果有任何建议，我将不胜感激。

我有 n 行，长度为 m。这些行具有具有一些预期总和的二进制 (0,1) 值。只要总和符合预期，1 就可以放在其行中的任何位置。目标是最小化长度为 m 的每一列的垂直总和。

例如，如果我们有 4 行和 10 列，则预期总和为：

Row 1: 6

Row 2: 7

Row 3: 4

Row 4: 5

可能的解决方案可能是：

1 1 1 1 1 1 0 0 0 0

1 1 1 0 0 0 1 1 1 1

1 0 0 1 1 1 0 0 0 0 

0 1 0 0 0 0 1 1 1 1

获取垂直总和：

3 3 2 2 2 2 2 2 2 2

反对把所有的都放在开头的大数:

1 1 1 1 1 1 0 0 0 0

1 1 1 1 1 1 1 0 0 0

1 1 1 1 0 0 0 0 0 0

1 1 1 1 1 0 0 0 0 0

总和为：

4 4 4 4 3 2 1 0 0 0

所以，我正在尝试分散负载。我的行数将进入 millions/billions，因此我希望使用线性代数方法而不是迭代方法。谢谢！

Answer 1

def create_min_vert_matrix(num_r, num_c, arr_sum_rows): 
    res = [] 
    curr = 0 
    for r in range(num_r): 
        row = [0]*num_c 
        while arr_sum_rows[r] > 0: 
            arr_sum_rows[r] -= 1 
            row[curr] = 1 
            curr = (curr+1)%num_c 
        res.append(row) 
    return res

快速测试：

create_min_vert_matrix(4, 10, [6,7,4,5])                                                                       
[[1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
 [1, 1, 1, 0, 0, 0, 1, 1, 1, 1],
 [0, 0, 0, 1, 1, 1, 1, 0, 0, 0],
 [1, 1, 0, 0, 0, 0, 0, 1, 1, 1]]

该函数采用行数 num_r、列数 num_c 和一个数组，该数组说明每行中的总和必须是多少（arr_sum_rows).

我们的想法是，如果我们尽可能均匀地按列分布，我们就能够最小化列总和。为了做到这一点，我们跟踪最后一列我们插入一个，curr，并且对于每个插入的一个增加它。如果它增长大于我们将其设置为零的列数：curr = (curr+1)%num_c.

算法在 O(n*m) 中运行，其中 n 和 m 是矩阵的行数和列数，如果我们 O(1) 额外 space不要计算结果所需的辅助 space（当然还有 O(n*m) 额外的 space）。

最小化合并行的垂直和的算法

Algorithm to minimize vertical sum of binned rows

algorithm

linear-algebra

minimization