3

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

我想迭代 M 个不同列表元素的子集（没有替换，顺序不重要），1 <= M <= N，根据它们的部分总和排序。M 不是固定的，最终结果应该考虑所有可能的子集。

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

我可以通过将 K 个迭代器 (1 <= M <= K) 放在一个最小堆中并让主迭代器在堆根上运行，将问题减少到固定大小 M 的子集。

本质上我需要 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,)]

回答：

正如大卫的回答所示，重要的技巧是要输出一个子集 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 为界。

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

4

1 回答 1

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)。

于 2012-08-11T20:26:41.430 回答