python - 算法以其产品的顺序获取列表的每个可能子集，而不构建和排序整个列表(即生成器)

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

本质上，这意味着我想按顺序迭代一组元素的幂集，我可以很容易地生成它，对其进行排序，然后完成。然而，功率集变得相当快，我预计我通常会想要第一个子集，我宁愿不生成一个包含数千个子集的列表，对它们进行排序，然后永远不要看第三个。这就是 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))