对于一组整数,获取总和大于某个值的所有集合

For a Set of Integers, Get All Sets Whose Sum is Greater Than Some Value

首先我要说的是,我发现很多问题和答案都回答了一些看似相关或接近这个问题,但实际上不是这个问题的问题。这似乎与硬币找零/子集总和问题有关,但我认为这明显不同,以至于子集总和答案不涵盖这个问题。

问题

假设我有一组 4 个整数,称为 S[1, 2, 5, 1]

目标是设计一组集合 G ,它由 S 的每个子集组成,其中set 大于某个值 N.

在此示例中,如果 N = 6,则 G 将是 [ [5,2,1,1], [5,2,1], [5,2], [5,1,1] ]

注意事项

我这里特地选了set这个词,因为每组的顺序根本不重要。 [5, 2, 1, 1] 等同于 [5, 1, 1, 2].

当您创建第一个超过 N 的集时,假设 G1,您还可以立即添加包含 G1 的所有其他集合作为子集。同样,如果你发现另一个新的集合G2,它还没有添加并且也超过了N,您可以立即添加所有包含 G2 的集合作为子集。您不需要检查这些集合的总和是否大于 N.

如果对S的所有成员求和且结果不大于N,则可以断定不存在集合符合条件。

实际用例

这里要实现的现实目标是我有一组项目,这些项目具有与之关联的数值权重,以及另一个代表阈值的值。我正在尝试找出当它们的权重相加时,是否可以例行地找到可以由超过阈值的项目组成的所有子组。

生成满足此条件的所有集合的最有效方法是什么?这个的复杂度是多少?

您可以使用 itertools 生成 sub-lists,然后根据条件筛选这些列表:

import itertools

input_list = [1, 2, 5, 1]
threshold = 6

result = []

for length in range(len(input_list) + 1):

    search_space = list(itertools.combinations(input_list, length))

    for item in search_space:
        if sum(item) > threshold:
            result.append(item)

print(result)

时间复杂度很高,首先需要生成每个长度的sub-lists(外层for循环),然后根据条件搜索正确的值(内层for循环),所以至少是O (n^2).

这是一个更高效的实现。值得注意的是:

  • 它正确地处理了重复的元素以避免返回相同的子集两次
  • 事实上,它通过将 same-valued 个元素分组到具有计数
  • 的容器中,从而完全避免了重新计算等效子集
  • 它从最大的子集(集合本身)开始,在保持在阈值以上的同时逐渐删除元素,early-exits以避免完全探索较小的子集
  • 它使用列表变异来避免昂贵的列表创建/处理,直到绝对必要
  • 它确实使用了递归,所以这里有一个小的性能损失,并且与所有递归一样:如果你向它抛出足够大的输入,它会引发错误。这是对 reader 的一个练习,如果这成为一个问题
  • 将其移植到迭代变体
from collections import Counter

def solve(nums, target):
    counts = sorted(Counter(nums).items())
    reserve = sum(nums) - target
    
    if reserve <= 0:
        return []
    return list(_solve(counts, reserve, []))

def _solve(counts, reserve, prefix):
    if not counts:
        yield tuple(prefix)
        return
    
    val, max_count = last = counts.pop()
    
    prefix.extend([val] * max_count)
    yield from _solve(counts, reserve, prefix)
    
    for count in range(1, max_count + 1):
        prefix.pop()
        if reserve - count * val > 0:
            yield from _solve(counts, reserve - count * val, prefix)
    
    counts.append(last)

计时:

from timeit import timeit

runs = 10
statement = "solve([randrange(15) for _ in range(25)], 100)"
setup = "from __main__ import solve; from random import randrange"
print(timeit(statement, setup=setup, number=runs)/runs)

输出:

0.22455865999218078

这意味着它能够在大约 225 毫秒内解决 25 个元素的问题,其中解决方案包含约 100k 个不同的子集。

我确实针对天真的解决方案对此进行了测试,以确保正确性。

关于时间复杂度,很难对此进行限制,因为它的 运行 时间实际上取决于数字的值(或者更确切地说,输出大小)。您可以将其绑定为 O(n log n + s * n),其中 n 是输入列表的大小,s 是输出列表的大小。