4

実際には、確率のあるオブジェクトのセットがあり、それらが独立していると仮定して、それらがすべて真である可能性が高い順に、つまり、次の降順で、それらの可能な各グループを調べたいと思います。サブセットの要素の積-または確率が同じ場合は長さの順に（（1、0.5）が（0.5）の後に来るように）。

例：[ 1, 0.5, 0.1 ]必要な場合[ (), (1), (0.5), (1, 0.5), (0.1), (1, 0.1), (0.5, 0.1), (1, 0.5, 0.1) ]

本質的に、これは、要素のセットのべき集合を順番に反復したいことを意味し、これをかなり簡単に生成し、並べ替えて、実行することができます。ただし、べき集合はかなり速く大きくなります。通常、最初のサブセットの1つが必要になると思います。何千ものサブセットのリストを生成して並べ替えてから、3番目のサブセットを超えないようにします。これは、Pythonジェネレーターが1日を節約できる場所です。

問題のより正式な仕様sorted(powerset(input), key = lambda l : reduce (lambda (p, n), e: (p * e, n-1), l, (1, 0)), reverse=True)として、ジェネレーターとして、またはリスト全体の作成と並べ替えを回避できるその他の方法を検討する必要があります。

これは、サブセット製品の問題とともに、ナップサック問題に関連していると合理的に確信していますが、機能する優れたアルゴリズムを取得するのに本当に苦労しています。助けていただければ幸いです:-)。最悪の場合（最後まで繰り返す）で全体を構築+並べ替えるよりも遅くなることは問題ではありません。必要なのは、はるかに優れた最良の場合（たとえば、最初の10％以内）のパフォーマンスだけです。

4

1 に答える 1

5

いい質問です。解決するのはかなり難しいです。組み合わせを順番に生成する方法も考えられませんがheapq、候補を並べ替えるために強力な（優先キューとも呼ばれる）を使用します。

from heapq import heappush, heappop
import operator

def prob(ps):
    """ returns the probability that *not* all ps are True """
    return 1-reduce(operator.mul, ps)

def gen(ps):
    # turn each to a tuple
    items = ((x,) for x in sorted(ps, reverse=True))

    # create a priority queue, sorted by probability
    pq = [(prob(x),x) for x in items]

    # because you wanted this
    yield ()

    # as long as there are valid combinations
    while pq:
        # get the best un-yielded combination, the pq makes sure of that
        p, x = heappop(pq)
        yield x

        # generate all the combinations from this item
        for other in ps:

            # keeping the tuples sorted -> unique combinations
            if other < x[-1]:

                # create a new combination
                new = x+(other,)
                item = prob(new), new

                # add it to the queue
                heappush(pq,item)


a = [1, 0.1, 0.5] 
print list(gen(a))
于 2011-02-24T23:41:54.833 に答える