将数组划分为几乎相等和的块。

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]]

- menbar

---

你有没有对分布的“均匀程度”有一个衡量标准？一种解决方案是对输入列表进行排序，然后为每个块选择n个元素中的1个。 - LoicM

这是一个少量整数的示例：[11,20,2,4,8,13,16,0,1,0,3,6] 期望输出为：[[20,1],[16,6],[13,8],[11,4,3,2]] 我是手动完成的，不知道如何编写代码。 - menbar

你能否编辑你的问题，包括最小可重现的示例？ - LoicM

这与多进程有什么关系？ - Anmol Singh Jaggi

好的，那么你已经知道了多进程的事情对吧？如果是的话，我建议你可以将多进程标签从问题中移除以消除混淆。 - Anmol Singh Jaggi

Answer 1

我们可以先尝试将数组分成两个部分，使它们的和几乎相等。
然后一旦我们有了这两组，我们可以进一步在每个组上应用相同的过程，以获得 2 * 2 = 4 个相等和的集合。

将一个数组分成两个近似相等的部分的算法如下:

• 初始化 2 个空集来保存我们的答案。
• 按相反的顺序对数组进行排序。
• 在保持 2 个集合的总和的情况下，遍历所有元素并将它们附加到总和较小的集合中。
• 请注意，这只是一个近似算法。如果我们想找到确切最优解，则可以将此问题建模为子集和问题，并查找是否可以将数组分成两个部分，其中一个集合的总和为sum/2 或 sum/2 - 1 或 sum/2 - 2 ... 0（按照这个顺序尝试每个）。这与我们的近似解决方案相比慢得多。

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”个拆分，我们可以使用堆(heap)：

• 创建大小为'n'的最小堆，每个元素都是形式为(current_sum_of_set_i, i)的元组。
• 因此，初始堆将包含元素(0, 0), (0, 1) ... (0, n-1)。
• 现在反向排序数组，将每个元素分配给堆顶上存在的集合(set)。
• 更新集合的堆元素(heap element)，以添加的新元素和它的新总和。

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

- Anmol Singh Jaggi

---

谢谢！有没有方法可以指定要分成多少块？在示例中，我说我需要4个块。如果我需要6个呢？是否有一种简单的方式来编写代码？非常感谢！ - menbar

更新了一个更通用的解决方案。在思考过程中感到很有趣 :) - Anmol Singh Jaggi

你能帮我用这种输入生成块吗？[[11，“a”]，[20，“a”]，[2，“a”]，[4，“a”]，[8，“a”]，[13，“a”]，[16，“a”]，[0，“a”]，[1，“a”]，[0，“a”]，[3，“a”]，[6，“a”]] 应该使用整数生成块，但列表中的字符串必须跟随整数吗？非常感谢！ - menbar

有没有办法在不改变顺序的情况下获得结果（这里使用了排序）？非常感谢。 - AkshayBandivadekar

@AkshayBandivadekar 我有一个解决方案，它尊重数组的顺序。 - Joost Döbken

Answer 2

以下是一个解决方案，其中每个块的总和小于或等于阈值。该解决方案受到Anmol Singh Jaggi提出的算法的启发。

在下面的函数中，输入集合被递归地分割，直到每个块的总和小于或等于阈值。

块的数量线性增加，但您可以根据自己的喜好进行更改，例如num_chunks = num_chunks*2。

def divide_almost_equally(arr, num_chunks,Threshold):
    divideMore = 0
    arr = sorted(arr, reverse=True)
    set_sum = np.zeros(num_chunks)
    sets = {}
    for i in range(num_chunks):
        sets[i] = []
    arr_idx = 0
    while arr_idx < len(arr):
        ChunkIndx = np.argmin(set_sum)
        sets[ChunkIndx].append(arr[arr_idx])
        set_sum[ChunkIndx] = set_sum[ChunkIndx] + arr[arr_idx]
        arr_idx = arr_idx + 1
    for total in set_sum:
        if(total>Threshold):
            divideMore = 1
            break
    if(divideMore == 1):
      num_chunks = num_chunks + 1
      return divide_almost_equally(arr, num_chunks,Threshold)
    else:
        return sets, num_chunks

if __name__ == "__main__":
   input = np.arange(0,100)
   Set, num_chunks = divide_almost_equally(np.arange(0,100), 1,100) # start with num_chunks = 1num_chunks = 1
   for chunk_indx in range(num_chunks): 
      print(Set[chunk_indx],'-- >',np.sum(Set[chunk_indx]))




 

- Mohamed Mahmoud

---

这种方法不尊重值的顺序。 - Joost Döbken

Answer 3

这里有一个通用解决方案，它将数组分割成几乎相等和的块，同时保持数组的顺序。

import math
from typing import Annotated, List


def split_equal_sum(arr: List[int], num_chunks: int) -> List[List[int]]:
    if num_chunks > len(arr):
        raise ValueError(
            f"Cannot split array of length {len(arr)} into {num_chunks} chunks."
        )

    def _split_in_two(
        arr: List[int], sleft: int = 1, sright: int = 1
    ) -> Annotated[List[int], 2]:
        left, right = arr[:sleft], arr[-sright:]
        for i in range(sleft + sright, len(arr)):
            if (sum(left) * sright) >= (sum(right) * sleft):
                right = arr[-len(right) - 1 :]
            else:
                left = arr[: len(left) + 1]
        return [left, right]

    if num_chunks > 1:
        sleft, sright = math.floor(num_chunks / 2), math.ceil(num_chunks / 2)
        left, right = _split_in_two(arr, sleft, sright)
        return split_equal_sum(left, sleft) + split_equal_sum(right, sright)
    return [arr]

`_split_in_two`是一个辅助方法，它将数组分成两个具有相等和的块，允许相对块权重。因此，如果我们要将数组分成三个块`A, B, C`，我们可以通过以下两个步骤完成：

AB, C = _split_in_two(values, 2, 1) # AB is twice the sum of C
A, B = _split_in_two(AB, 1, 1)

和 split_equal_sum 不断地将数组分割，直到所有的 num_chunks 都等于1为止：

>>> split_equal_sum([11, 20, 2, 4, 8, 13, 16, 0, 1, 0, 3, 6], 4)
[[11, 20], [2, 4, 8], [13], [16, 0, 1, 0, 3, 6]]

考虑了奇数分布，所以例如 `split_equal_sum([1, 1, 8], 3)` 仍然可以。

- Joost Döbken