按乘积顺序获取列表的每个可能子集的算法，无需构建和排序整个列表（即生成器）

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 生成器有望拯救世界的地方！

问题的更正式规范，我需要找出一种方法来排序（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))