3

L[0]からL[N-1]の昇順でソートされたN個の正の数のリストがあります。

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,)]

答え：

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]

UPDATE、O(K log K) アルゴリズムを見つけました。

これは上記のトリックに似ていますが、サブセットの最大値を超える要素が追加されたすべての 1 要素拡張を追加する代わりに、2 つの拡張のみを考慮します。1 つは max(S)+1 を追加し、もう 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 で制限されることに注意してください。

プライオリティキューの代わりにプライオリティ デキュー (min-max ヒープ)を使用することで、さらに改善できる可能性がありますが、率直に言って、このソリューションには満足しています。ただし、線形アルゴリズム、またはそれが不可能であることの証明に興味があります。

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 に答える