按照產品的順序獲取列表中每個可能子集的算法，無需構建和整理整個列表（即發電機）

Question

實際上，我有一組具有概率的對象，我想看看每個可能的一組，他們是多麼可能是他們是所有假設他們是獨立的 - 即按子集的元素的乘積的降序 - 或按照長度的順序，如果概率是一樣的（所以（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) ]

從本質上說，這意味着我要遍歷一組以元素的冪，我可以很容易產生這一點，排序，並完成。但是，powersets的速度非常快，我希望我通常會想要第一個子集中的一個，而我不想生成數千個子集的列表，排序它們，然後再從第三個子集開始。這是python生成器希望節省一天的地方！

問題的更正式的說明，我需要找出一種方法來做sorted(powerset(input), key = lambda l : reduce (lambda (p, n), e: (p * e, n-1), l, (1, 0)), reverse=True)，作爲一個生成器，或以其他方式讓我避免構建和整理整個列表。

我相當肯定這是與揹包問題以及子集產品問題有關，但我真的很努力地爲它找到一個很好的算法，幫助將非常感激:-) 。在最糟糕的情況下（比如一直迭代到最後），它不是一個比構建+整理更慢的問題，它只需要更好的最佳情況（前10％，比如說）的性能。

Answer 1

不錯的問題，解決起來相當棘手。我想不出按照順序生成組合的方法，但我使用強大的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))