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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – 按照产品顺序获取列表的每个可能子集的算法,无需构建和排序整个列表(即生成器)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1834字，纯文字阅读大概需要3分钟。

内容图文

实际上,我有一组具有概率的对象,我想看看它们中的每一个可能的组,按照它们是否可能的假设它们是独立的可能性 – 即按照从的顺序降序子集元素的乘积 – 或者如果概率相同则按长度顺序(使得(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生成器希望挽救这一天的地方！

更正式的问题说明,我需要找出一种方法来排序(powerset(输入),key = lambda l：reduce(lambda(p,n),e：(p * e,n-1),l ,(1,0)),reverse = True),作为生成器,或以其他方式让我避免构建和排序整个列表.

我有理由相信这与背包问题以及子集产品问题有关,但我真的很难为它获得一个很好的算法,并且非常感谢帮助:-).这不是一个问题,因为它比在最坏的情况下构建排序整个过程要慢(迭代一直到最后),它只需要更好的最佳情况(在前10％,比如说)性能.

解决方法:

好问题,解决起来相当棘手.我想不出按顺序生成组合的方法,但是我使用强大的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))

内容总结

以上是互联网集市为您收集整理的python – 按照产品顺序获取列表的每个可能子集的算法,无需构建和排序整个列表(即生成器)全部内容，希望文章能够帮你解决python – 按照产品顺序获取列表的每个可能子集的算法,无需构建和排序整个列表(即生成器)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---