python利用递归方法实现求集合的幂集
作者:精灵之子 时间:2023-06-10 09:38:12
什么是集合的幂集?
就是原集合中所有的子集(bai包括全集du和空集)构成的集族。可数集是zhi最小的无限集; 它的幂集和实数dao集一一对应(也称同势),是不可数集。
不是所有不可数集都和实数集等势,集合的势可以无限的大。如实数集的幂集也是不可数集,但它的势比实数集大。 设X是一个有限集,|X| = k,则X的幂集的势为2的k次方。
代码
def powSet(S):
#创建列表a存储S中的元素
a=[]
for i in S:
a.append(i)
#判断S中是否只有一个元素,作为递归的终点
if len(a)==1:
return set([frozenset(),frozenset(a)])
powset=set()
#遍历S中的每一个元素
for i in range(len(a)):
S.remove(a[i])
temp = set()
#取S中的这一个元素去掉,得到集合S的下一层(相当于S-1),认为S-1幂集已知。
#将去掉的元素与S-1幂集中每一个元素都求并,得到新集合temp,temp和S-1的幂集求并便得到S的幂集
for j in powSet(S):
temp.add(j.union({a[i]}))
powset = powSet(S).union(temp)
S.add(a[i])
return powset
#验证
s=set([1,2,3])
print(powSet(s))
#结果
{{frozenset({2}), frozenset({2, 3}), frozenset({1, 2}), frozenset({1, 2, 3}), frozenset({3}), frozenset({1}), frozenset(), frozenset({1, 3})}}
需要知识
幂集的概念
python set 和 frozenset 数据类型
心得体会
笔者在写代码时遇到的问题是认为powSet(S-1)(S-1代表S中去掉任一个元素)就完完全全地替代了真正去掉那一个随机元素的元素组成的幂集。
实际上这样是不完全的,因为设置的递归规则有缺陷,不可能完全遍历所有情况。
解决:借助于集合元素的不可重复添加这一特性,我们可以遍历遍历所有S中的元素,都让它们进行一次递归操作,这样做虽然会产生n(S)次重复,但是它可以考虑到所有情况。
来源:https://blog.csdn.net/zk280big100/article/details/108429186
标签:python,递归,集合
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Golang二维切片初始化的实现
2024-05-09 14:57:54
Python实现爬取逐浪小说的方法
2022-05-26 22:31:29
django foreignkey外键使用的例子 相当于left join
2021-04-17 15:52:33
使用SpringBoot + Redis 实现接口限流的方式
2023-07-11 00:06:49
Python判断字符串是否包含特定子字符串的多种方法(7种方法)
2021-09-20 02:22:51
初学者必读:经典的数据库记录分页代码
2009-01-08 15:27:00
多浏览器兼容的动态加载 JavaScript 与 CSS第1/2页
2024-05-13 09:20:31
Python 实现数组相减示例
2021-08-19 07:01:52
详解阿里云视频直播PHP-SDK接入教程
2023-11-21 02:19:17
![](https://img.aspxhome.com/file/2023/1/111351_0s.png)
php json_encode与json_decode详解及实例
2023-07-04 22:46:27
教程:纯CSS作的小灯笼效果
2008-08-26 17:22:00
![](https://img.aspxhome.com/file/UploadPic/20088/26/2008826173212465s.gif)
教你如何6秒钟往MySQL插入100万条数据的实现
2024-01-19 02:17:35
![](https://img.aspxhome.com/file/2023/7/105667_0s.jpg)
python列表:开始、结束、步长值实例
2022-03-06 06:59:48
![](https://img.aspxhome.com/file/2023/7/133857_0s.jpg)
Python 编程语言详细介绍
2022-08-21 08:39:27
![](https://img.aspxhome.com/file/2023/1/92121_0s.jpg)
网站升级兼容firefox经验小谈
2007-10-28 20:28:00
![](https://img.aspxhome.com/file/UploadPic/up/2007102823141550.jpg)
SQL查询的底层运行原理深入分析
2024-01-21 04:43:49
python判断所输入的任意一个正整数是否为素数的两种方法
2022-02-26 12:43:14
pywinauto自动化测试使用经验
2022-12-21 02:36:10
微信小程序 scroll-view实现上拉加载与下拉刷新的实例
2024-04-23 09:30:40
![](https://img.aspxhome.com/file/2023/7/135487_0s.gif)
Javascript 面试题随笔
2024-04-29 13:44:53