根据产品顺序获取列表的每个可能子集的算法,无需构建和排序整个列表(即生成器)

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

从本质上讲,这意味着我想按顺序遍历一组元素的powerset,我可以相当容易地生成它,对它进行排序,并完成.然而,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))