arrays - 前 K 个子集总和,没有排序
问题描述
给定一个大小为 N 的数组,(0<K<=N)
按元素和的递增顺序打印大小为 K 的所有子集
Array:
[6,8,3,9], N=4, K=3
Sorted Subsets:
[3, 6, 8] (sum=17)
[3, 6, 9] (sum=18)
[3, 8, 9] (sum=20)
[6, 8, 9] (sum=23)
我不需要整个排序列表,而是需要前 T 个条目(T 很小)。列出所有子集(nCk)并对它们进行排序对于大 N 来说非常昂贵。有没有办法在不实际枚举所有子集的情况下获得前 T 个子集?我正在考虑选择最小的 K 元素,这是最小的子集,然后找到一种方法来通过替换一个或多个元素来获得下一个最小的子集,但是替换的选择又太多了。
解决方案
我会这样解决这个问题:
- 对数组进行排序,让
s
成为第一个k
元素的总和。 - 生成 sum 的所有子集,等于
s
使用回溯搜索。 - 使用分支定界算法找到最小的
s2 > s
使得存在总和等于 的子集。s2
- 如果有
s2
,则设置s = s2
并转到步骤2。否则,停止。
这是 Python 中的一个实现:它按总和的顺序懒惰地生成每个子集,因此您可以只取它产生的前 T 个子集。
def subsets_in_sum_order(lst, k):
"""
Returns a generator yielding the k-element subsets
of lst, in increasing order of their sum.
"""
lst = sorted(lst)
s = sum(lst[:k])
max_s = sum(lst[-k:])
while s is not None:
yield from subsets_of_sum(lst, k, s)
s = smallest_sum_in_range(lst, k, s+1, max_s)
def subsets_of_sum(lst, k, s, t=(), i=0):
"""
Returns a generator yielding tuples t + tt, where tt
is a k-element subset of lst[i:] whose sum is s. The
subsets are yielded in lexicographic order. The list
lst must be sorted.
"""
if k < 0:
raise ValueError()
elif k == 0:
if s == 0:
yield t
else:
for j in range(i, len(lst) - k + 1):
if sum(lst[j:j+k]) > s: break
v = lst[j]
s2 = s - v
t2 = t + (v,)
yield from subsets_of_sum(lst, k-1, s2, t2, j+1)
def smallest_sum_in_range(lst, k, min_s, max_s, i=0):
"""
Returns the smallest s such that min_s <= s <= max_s,
and there is a k-element subset of lst[i:] with sum s.
The list lst must be sorted.
Returns None if there is no such s.
"""
result = None
if k < 0:
raise ValueError()
elif k == 0:
if min_s <= 0:
result = 0
elif min_s <= max_s and sum(lst[-k:]) >= min_s:
for j in range(i, len(lst) - k + 1):
v = lst[j]
if k * v > max_s: break
s = smallest_sum_in_range(lst, k-1, min_s-v, max_s-v, j+1)
if s is not None:
s += v
result = s
max_s = s - 1
return result
例子:
>>> subsets = subsets_in_sum_order([1, 2, 3, 4, 5], 3)
>>> for subset in subsets:
... print(subset, sum(subset))
...
(1, 2, 3) 6
(1, 2, 4) 7
(1, 2, 5) 8
(1, 3, 4) 8
(1, 3, 5) 9
(2, 3, 4) 9
(1, 4, 5) 10
(2, 3, 5) 10
(2, 4, 5) 11
(3, 4, 5) 12
@user3386109 观察到,如果列表长度远大于您要生成的子集的数量,那么我们实际上不需要整个列表,因为列表中较大的元素不会出现在前 T 个子集中. 前 T 个子集必须只使用列表中的前 T + k - 1 个元素,因此我们可以通过使用来提高效率heapq.nsmallest
:
import heapq
from itertools import islice
def smallest_subsets(lst, k, num_subsets):
lst = heapq.nsmallest(num_subsets + k - 1, lst)
subsets = subsets_in_sum_order(lst, k)
return islice(subsets, num_subsets)
这使您不必对长度为 N 的整个列表进行排序。但是,回溯搜索和分支定界算法并没有从中受益太多,因为它们都已经使用总和的界限来尽早消除分支。当 T 很小时,两者都不需要迭代到长列表的末尾。
推荐阅读
- java - spring mvc,我的 bean 如何在控制器中自动装配?
- java - 用于完整应用程序性能测试的 Java JMH 工具
- java - 我需要 log4j 1.2 和 2.5 在同一个 webapp 中共存
- python - Python3.7 input() 连接整数
- perl - Mojolicious 从一分钟到下一分钟突然停止工作
- java - OnItemLongClickListener 在释放按钮时也会运行 OnItemClickListener
- javascript - Javascript中对象数据的更快序列化/反序列化?
- airflow - 气流审核日志
- bash - 使用ffmpeg在循环中更改bash变量
- c# - 在 ASP.Net 核心中将所有 Caps 属性名称的默认 camelCase 序列化为 JSON 的问题