algorithm - 对已排序部分和的高效迭代

Question

我有一个按升序排列的 N 个正数列表，L[0] 到 L[N-1]。

我想遍历 M 个不同列表元素的子集(没有替换，顺序不重要)，1 <= M <= N，根据它们的部分和排序。 M不固定，最终结果要考虑所有可能的子集。

我只想要 K 个最小的子集(理想情况下是 K 中的多项式)。枚举 M <= K 的所有子集的明显算法是 O(K!)。

我可以将问题简化为固定大小 M 的子集，方法是将 K 个迭代器 (1 <= M <= K) 放在最小堆中，并让主迭代器在堆根上运行。

本质上我需要 Python 函数调用:

sorted(itertools.combinations(L, M), key=sum)[:K]

...但高效(N ~ 200，K ~ 30)，应该在不到 1 秒内运行。

示例:

L = [1, 2, 5, 10, 11]
K = 8
answer = [(1,), (2,), (1,2), (5,), (1,5), (2,5), (1,2,5), (10,)]

答案:

正如 David 的回答所示，重要的技巧是对于要输出的子集 S，S 的所有子集必须先前已输出，特别是仅删除 1 个元素的子集。因此，每次输出一个子集时，您可以添加该子集的所有 1 元素扩展以供考虑(最大为 K)，并且仍然确保下一个输出子集将在所有考虑子集的列表中直到这个点。

功能齐全、效率更高的 Python 函数:

def sorted_subsets(L, K):
  candidates = [(L[i], (i,)) for i in xrange(min(len(L), K))]

  for j in xrange(K):
    new = candidates.pop(0)
    yield tuple(L[i] for i in new[1])
    new_candidates = [(L[i] + new[0], (i,) + new[1]) for i in xrange(new[1][0])]
    candidates = sorted(candidates + new_candidates)[:K-j-1]

更新，发现了一个复杂度为 O(K log K) 的算法。

这类似于上面的技巧，但不是添加所有元素大于子集最大值的 1 元素扩展，而是只考虑 2 个扩展:一个添加 max(S)+1，另一个另一个将 max(S) 移动到 max(S) + 1(最终会向右生成所有 1 元素扩展)。

import heapq

def sorted_subsets_faster(L, K):
  candidates = [(L[0], (0,))]

  for j in xrange(K):
    new = heapq.heappop(candidates)
    yield tuple(L[i] for i in new[1])
    i = new[1][-1]
    if i+1 < len(L):
      heapq.heappush(candidates, (new[0] + L[i+1], new[1] + (i+1,)))
      heapq.heappush(candidates, (new[0] - L[i] + L[i+1], new[1][:-1] + (i+1,)))

根据我的基准测试，它对于 K 的所有值都更快。

另外，不需要提前提供K的值，我们可以迭代并随时停止，而不会改变算法的效率。另请注意，候选人的数量以 K+1 为界。

通过使用优先级双端队列(最小-最大堆)而不是优先级队列可能会进一步改进，但坦率地说，我对这个解决方案很满意。不过，我会对线性算法感兴趣，或者对它不可能的证明感兴趣。

Answer 1

这是一些粗略的 Python 式伪代码:

final = []
L = L[:K]    # Anything after the first K is too big already
sorted_candidates = L[] 
while len( final ) < K:
    final.append( sorted_candidates[0] )  # We keep it sorted so the first option
                                          # is always the smallest sum not
                                          # already included
    # If you just added a subset of size A, make a bunch of subsets of size A+1
    expansion = [sorted_candidates[0].add( x ) 
                   for x in L and x not already included in sorted_candidates[0]]

    # We're done with the first element, so remove it
    sorted_candidates = sorted_candidates[1:]

    # Now go through and build a new set of sorted candidates by getting the
    # smallest possible ones from sorted_candidates and expansion
    new_candidates = []
    for i in range(K - len( final )):
        if sum( expansion[0] ) < sum( sorted_candidates[0] ):
            new_candidates.append( expansion[0] )
            expansion = expansion[1:]
        else:
            new_candidates.append( sorted_candidates[0] )
            sorted_candidates = sorted_candidates[1:]
    sorted_candidates = new_candidates

我们假设您将以高效的方式执行诸如删除数组的第一个元素之类的操作，因此循环中唯一真正的工作是构建扩展和重建 sorted_candidates。这两个步骤都少于 K 步，因此作为上限，您正在查看的循环为 O(K) 并且运行了 K 次，因此算法的 O(K^2)。