子集总和等于或接近给定比率的随机分区的快速 Python 算法

Question

这个问题是我上一个问题的延伸：快速 python 算法从子集总和等于比率的数字列表中找到所有可能的分区。我想划分一个数字列表，使子集总和的比率等于给定值。不同之处在于，现在我有一长串 200 个数字，因此枚举是不可行的。请注意，虽然列表中当然有相同的数字，但每个数字都是可区分的。

import random
lst = [random.randrange(10) for _ in range(200)]

在这种情况下，我想要一个函数来随机采样一定数量的分区，其子集总和等于 或接近 给定的比率。这意味着解决方案可能不是最优的，但我需要算法足够快。我想贪心算法会做。话虽如此，当然如果有一个比较快的算法可以给出最优解就更好了。

例如，我想对 100 个分区进行采样，所有分区的子集和比率均为 4 : 3 : 3。允许重复分区，但对于这么长的列表应该不太可能。该函数应该这样使用：

partitions = func(numbers=lst, ratios=[4, 3, 3], num_gen=100)

要测试解决方案，您可以执行以下操作：

from math import isclose
eps = 0.05
assert all([isclose(ratios[i] / sum(ratios), sum(x) / sum(lst), abs_tol=eps) 
            for part in partitions for i, x in enumerate(part)])

有什么建议吗？

Answer 1

您可以使用贪婪的启发式方法，根据列表的 num_gen 随机排列生成每个分区。每个随机排列被划分为 len(ratios) 个连续的子列表。分区子集是排列的子列表这一事实使得在子列表生成期间执行比率条件非常容易：一旦我们当前正在构建的子列表的总和达到其中一个比率，我们就“完成”子列表，添加它到分区并开始创建一个新的子列表。我们可以一次性完成整个排列，从而得到以下时间复杂度算法 O(num_gen * len(lst)).

M = 100

N = len(lst)
P = len(ratios)
R = sum(ratios)
S = sum(lst)

for _ in range(M):
    # get a new random permutation
    random.shuffle(lst)
    
    partition = []
    
    # starting index (in the permutation) of the current sublist
    lo = 0
    # permutation partial sum
    s = 0
    # index of sublist we are currently generating (i.e. what ratio we are on)
    j = 0
    # ratio partial sum
    rs = ratios[j]
    
    for i in range(N):
        s += lst[i]
        
        # if ratio of permutation partial sum exceeds ratio of ratio partial sum,
        # the current sublist is "complete"
        if s / S >= rs / R:
            partition.append(lst[lo:i + 1])
            # start creating new sublist from next element
            lo = i + 1
            j += 1
            if j == P:
                # done with partition
                # remaining elements will always all be zeroes 
                # (i.e. assert should never fail)
                assert all(x == 0 for x in lst[i+1:])
                partition[-1].extend(lst[i+1:])
                break
            rs += ratios[j]

请注意，可以将外部循环重新设计为无限循环，直到生成 num_gen 次良好的分区（而不是仅仅循环 num_gen 次）以获得更高的鲁棒性。该算法预计在 O(M) 次迭代中产生 M 个良好的分区（前提是 random.shuffle 足够随机）如果良好分区的数量与分区的总数相比不太小大小相同，因此对于大多数输入它应该表现良好。对于像 [random.randrange(10) for _ in range(200)] 这样的（几乎）均匀随机列表，每个迭代都会产生一个带有 eps = 0.05 的良好分区，如下面的示例运行所示。当然，算法的性能如何也将取决于 'good' 的定义——接近度要求越严格（换句话说，epsilon 越小），找到好的分区所需的迭代次数就越多。可以找到此实现 here，并且适用于任何输入（假设 random.shuffle 最终生成输入列表的 all 排列）。

您可以找到代码的可运行版本（带有断言来测试分区的“好”程度）here。

子集总和等于或接近给定比率的随机分区的快速 Python 算法

Fast Python algorithm for random partitioning with subset sums equal or close to given ratios

python

algorithm

subset

greedy

subset-sum