python – 修剪基于集合的组合列表
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – 修剪基于集合的组合列表,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2268字,纯文字阅读大概需要4分钟。
内容图文
![python – 修剪基于集合的组合列表](/upload/InfoBanner/zyjiaocheng/788/88d7ccd77b8b43b0a168f2a2c03587b5.jpg)
虽然这个问题是使用Python编程语言制定的,但我认为它更多的是编程逻辑问题.
我列出了所有可能的组合,即:n选择k
我可以使用准备这样的列表
import itertools
bits_list = list(itertools.combinations(range(n), k))
如果’n’为100,且’k’为5,则’bits_list’的长度为75287520.
现在,我想修剪这个列表,这样数字就会出现在组中,或者它们不会出现.我们以下面的集合为例:
设置1:[0,1,2]
第2集:[57,58]
第3集:[10,15,20,25]
第4集:[10,11,12,13,14,15,16,17,18,19]
这里每个集合需要一起出现在bits_list的任何成员中,或者根本不出现.
到目前为止,我只能想到一个解决这个问题的蛮力if-else方法,但if-else条件的数量会非常大.
这就是我所拥有的:
bits_list = [x for x in list(itertools.combinations(range(n), k))
if all(y in x for y in [0, 1, 2]) or
all(y not in x for y in [0, 1, 2])]
现在,这只涵盖了Set 1.我想为很多套这样做.如果集合的长度长于k的值,我们可以忽略该集合(例如,k = 5和Set 4).
注意,最终目标是让’k’迭代一个范围,比如说[5:25]并对附加列表进行处理.列表的大小在这里呈指数级增长,从计算上讲,非常昂贵!
当’k’为10时,python解释器在完成任何普通笔记本电脑16 GB RAM之前中断该过程.我需要找到一个适合相对现代服务器(不是集群或服务器场)的内存的解决方案.
任何帮助是极大的赞赏!
P.S.:直观地说,将这个问题视为为登上公共巴士或火车系统的人提供所有可能的案例.通常,您登上整个团体,或者您没有登上任何人.
更新:
>对于上面给定的集合,如果k = 5,则bits_list的有效成员将是[0,1,2,57,58],即:Set1和Set2的组合.如果k = 10,那么我们可以将Set1 Set2 Set3 NoSetElement构建为可能的成员. @DonkeyKong的解决方案让我意识到我没有在我的问题中明确提到这一点.
>我有很多套;我打算使用足够的集合来修剪完整的组合列表,以使bits_list最终适合内存.
> @ 9000的建议在这里完全有效,在每次迭代中,我可以将组合保存为实际位.
解决方法:
在某个点(大约n = 90,k = 5),这仍然会被内存错误(我不知道你是如何从列表中躲避)中摧毁,但它比你目前的实施.对于n = 80和k = 5,我的基本基准测试使我的解决方案在2.6秒,而你的解决方案在52秒左右.
我们的想法是分别构建过滤器的不相交和子集部分.不相交的部分是微不足道的,子集部分是通过获取长度为k-set_len的所有不相交组合的itertools.product和你的集合的各个元素来计算的.
from itertools import combinations, product, chain
n = 80
k = 5
set1 = {0,1,2}
nots = set(range(n)) - set1
disj_part = list(combinations(nots, k))
subs_part = [tuple(chain(x, els)) for x, *els in
product(combinations(nots, k - len(set1)), *([e] for e in set1))]
full_l = disj_part + subs_part
内容总结
以上是互联网集市为您收集整理的python – 修剪基于集合的组合列表全部内容,希望文章能够帮你解决python – 修剪基于集合的组合列表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。