您可以使用贪婪启发式方法，从列表的 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 次）以获得更高的稳健性。如果良好分区的数量与该算法的分区总数相比不是太小，则该算法预计会在 M 次迭代中产生 O(M) 个良好的分区（假设 random.shuffle 足够随机）相同的大小，因此对于大多数输入它应该表现良好。对于像 [random.randrange(10) for _ in range(200)] 这样的（几乎）均匀随机列表，每次 迭代都会产生一个带有 eps = 0.05 的良好分区，通过运行下面的示例可以明显看出。当然，算法的表现如何还取决于“好”的定义——紧密度要求越严格（换句话说，epsilon 越小），找到一个好的分区所需的迭代次数就越多。此实现可以在 here 中找到，并且适用于任何输入（假设 random.shuffle 最终生成输入列表的 all 排列）。

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