전체 목록을 작성하고 정렬하지 않고 제품의 순서대로 목록의 모든 가능한 부분 집합을 얻는 알고리즘 (예 : 생성자)

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은 꽤 빠르며, 보통 첫 번째 하위 집합 중 하나를 원할 것으로 기대합니다. 그리고 수천 개의 하위 집합 목록을 생성하고 정렬 한 다음 세 번째 집합을 살펴 보지 않을 것입니다. 이것은 파이썬 생성기가 희망적으로 하루를 절약하는 곳입니다!

더 공식적인 사양으로, 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))