对于一组整数,获取总和大于某个值的所有集合
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
是输出列表的大小。
首先我要说的是,我发现很多问题和答案都回答了一些看似相关或接近这个问题,但实际上不是这个问题的问题。这似乎与硬币找零/子集总和问题有关,但我认为这明显不同,以至于子集总和答案不涵盖这个问题。
问题
假设我有一组 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
是输出列表的大小。