python – 生成无限序列的有序元组
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – 生成无限序列的有序元组,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2196字,纯文字阅读大概需要4分钟。
内容图文
我有两个生成器genA和genB,它们每个都生成一个无限的,严格单调递增的整数序列.
现在我需要一个生成所有元组(a,b)的生成器,使得a由genA生成,b由genB生成,并且< b,按b递增排序.在模糊性的情况下,排序并不重要,即如果b == c d,则首先生成(a,b)或首先生成(c,d)无关紧要. 例如.如果genA和genB都生成素数,则新生成器应生成:
(2, 3), (2, 5), (3, 5), (2, 7), (3, 7), (5, 7), (2, 11), ...
如果genA和genB是有限列表,则压缩然后排序就可以了.
适用于形式(x,b)的所有元组,以下成立:第一(genA)< = x< = max(genA,b)< = b,是genA和max生成的第一个元素的第一个(genA) (genA,b)genA生成的最后一个元素,小于b. 这是我走了多远.有关如何以所述方式组合两台发电机的任何想法?
解决方法:
如果不保存genA的所有结果,我认为不可能这样做.解决方案可能如下所示:
import heapq
def gen_weird_sequence(genA, genB):
heap = []
a0 = next_a = next(genA)
saved_a = []
for b in genB:
while next_a < b:
saved_a.append(next_a)
next_a = next(genA)
# saved_a now contains all a < b
for a in saved_a:
heapq.heappush(heap, (a+b, a, b)) #decorate pair with sorting key a+b
# (minimum sum in the next round) > b + a0, so yield everything smaller
while heap and heap[0][0] <= b + a0:
yield heapq.heappop(heap)[1:] # pop smallest and undecorate
说明:主循环简单地遍历genB中的所有元素,然后从genA获取小于b的所有元素并将它们保存在列表中.然后它生成所有元组(a0,b),(a1,b),…,(a_n,b)并将它们存储在min-heap中,这是一个有效的数据结构,当你只想提取最小值时集合的价值.与排序一样,您可以执行trick不保存对本身,但在它们前面添加您要排序的值(a b),因为元组之间的比较将通过比较第一项来开始.最后,它弹出堆中的所有元素,其总和保证小于为下一个b生成的任何对的总和并产生它们.
请注意,当您生成结果时,heap和saved_a都会增加,我想与目前生成的元素数量的平方根成比例.
使用一些素数进行快速测试:
In [2]: genA = (a for a in [2,3,5,7,11,13,17,19])
In [3]: genB = (b for b in [2,3,5,7,11,13,17,19])
In [4]: for pair in gen_weird_sequence(genA, genB): print pair
(2, 3)
(2, 5)
(3, 5)
(2, 7)
(3, 7)
(5, 7)
(2, 11)
(3, 11)
(2, 13)
(3, 13)
(5, 11)
(5, 13)
(7, 11)
(2, 17)
(3, 17)
(7, 13)
正如所料.用无限发电机测试:
In [11]: from itertools import *
In [12]: list(islice(gen_weird_sequence(count(), count()), 16))
Out[12]: [(0, 1), (0, 2), (0, 3), (1, 2), (0, 4), (1, 3), (0, 5), (1, 4),
(2, 3), (0, 6), (1, 5), (2, 4), (0, 7), (1, 6), (2, 5), (3, 4)]
内容总结
以上是互联网集市为您收集整理的python – 生成无限序列的有序元组全部内容,希望文章能够帮你解决python – 生成无限序列的有序元组所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。