将数组分成几乎相等和的块

Question

用于划分块的代码由以下代码段提供：

def chunks(lst, n):     #n here is 4
    """Yield successive n-sized chunks from lst."""
    for i in range(0, len(lst), n):
        yield lst[i:i + n]

作为输入，我有一个包含以下整数的列表：

[11, 45, 74, 24, 27, 55, 37, 97, 15, 36, 54, 7, 41, 77, 28, 36, 22, 214, 110, 40, 41, 14, 6, 35, 6, 7, 62, 2, 34, 1, 30, 5, 4, 8, 9, 7, 5, 7, 0, 0, 3, 0, 0, 1, 2]

我想用它生成4个块。作为输出，我得到以下结果：

[[11, 45, 74, 24, 27, 55, 37, 97, 15, 36, 54, 7], 
[41, 77, 28, 36, 22, 214, 110, 40, 41, 14, 6, 35], 
[6, 7, 62, 2, 34, 1, 30, 5, 4, 8, 9, 7], 
[5, 7, 0, 0, 3, 0, 0, 1, 2]]

我的问题是，输出中的第二个列表的权重高于其他列表；这些数字的分布不太公平。
有谁能告诉我如何通过包含整数来获得数据在数据块中的公平分布

我亲手做了一个例子：

输入：[11,20,2,4,8,13,16,0,1,0,3,6]

输出：[[20,1,0,0],[16,6],[13,8],[11,4,3,2]]

Answer 1

我们可以首先尝试将数组分成两部分，使其总和几乎相等。
一旦我们有了这两个集合，我们就可以对每个集合应用相同的过程，得到2*2=4个相等和的集合

将数组划分为近似相等和的两部分的算法如下所示：

• 初始化2个空集合以保存我们的答案
• 按相反顺序对数组排序
• 在保持两个集合的总和的同时，迭代数组中的所有元素，并将它们附加到总和较小的集合中
• 请注意，这只是一个近似算法。如果我们想找到精确的最优答案，那么我们可以将这个问题建模为subset sum problem，并找出我们是否可以将数组分成两部分，其中一部分的和是sum/2或sum/2 - 1或sum/2 - 20（按顺序尝试每一个）。这比我们的近似解要慢得多

def divide_almost_equally_into_2(arr):
    set1 = []
    set2 = []
    sum1 = sum2 = arr_idx = 0
    while arr_idx < len(arr):
        if sum1 < sum2:
            set1.append(arr[arr_idx])
            sum1 += arr[arr_idx]
        else:
            set2.append(arr[arr_idx])
            sum2 += arr[arr_idx]
        arr_idx += 1
    return set1, set2


def divide_almost_equally_into_4(arr):
    arr.sort(reverse=True)
    set1, set2 = divide_almost_equally_into_2(arr)
    set11, set12 = divide_almost_equally_into_2(set1)
    set21, set22 = divide_almost_equally_into_2(set2)
    return [set11, set12, set21, set22]


def main():
    arr = [11,20,2,4,8,13,16,0,1,0,3,6]
    set1, set2, set3, set4 = divide_almost_equally_into_4(arr)
    print(f"{arr}   {sum(arr)}\n")
    print(f"{set1}   {sum(set1)}")
    print(f"{set2}   {sum(set2)}")
    print(f"{set3}   {sum(set3)}")
    print(f"{set4}   {sum(set4)}")


main()

输出：

[20, 16, 13, 11, 8, 6, 4, 3, 2, 1, 0, 0]   84

[13, 8]   21
[16, 3, 2]   21
[11, 6, 4]   21
[20, 1, 0, 0]   21

编辑：

为了将相同的算法推广到“n”个拆分，我们可以使用堆：

• 创建一个大小为“n”的最小堆，其中每个元素都是一个形式的元组（当前集合的总和）
• 因此，最初堆将包含元素(0, 0), (0, 1) ... (0, n-1)
• 现在迭代反向排序数组，并将每个元素分配给堆顶部的集合
• 使用添加到集合中的元素的新总和更新集合的heap元素

import heapq


def divide_almost_equally(arr, num_chunks):
    arr = sorted(arr, reverse=True)
    heap = [(0, idx) for idx in range(num_chunks)]
    heapq.heapify(heap)
    sets = {}
    for i in range(num_chunks):
        sets[i] = []
    arr_idx = 0
    while arr_idx < len(arr):
        set_sum, set_idx = heapq.heappop(heap)
        sets[set_idx].append(arr[arr_idx])
        set_sum += arr[arr_idx]
        heapq.heappush(heap, (set_sum, set_idx))
        arr_idx += 1
    return sets.values()


def main():
    arr = [11,20,2,4,8,13,16,0,1,0,3,6]
    set1, set2, set3, set4 = divide_almost_equally(arr, 4)
    print(f"{sorted(arr, reverse=True)}   {sum(arr)}\n")
    print(f"{set1}   {sum(set1)}")
    print(f"{set2}   {sum(set2)}")
    print(f"{set3}   {sum(set3)}")
    print(f"{set4}   {sum(set4)}")


main()

输出：

[20, 16, 13, 11, 8, 6, 4, 3, 2, 1, 0, 0]   84

[20, 1]   21
[16, 4, 0, 0]   20
[13, 6, 3]   22
[11, 8, 2]   21