python利用递归方法实现求集合的幂集

什么是集合的幂集?

就是原集合中所有的子集（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)次重复，但是它可以考虑到所有情况。

到此这篇关于python利用递归方法实现求集合的幂集的文章就介绍到这了,更多相关python递归方法求集合的幂集内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • python3中set（集合）的语法总结分享

    介绍 set 顾明思义,就是个集合,集合的元素是唯一的,无序的.一个{ }里面放一些元素就构成了一个集合,set里面可以是多种数据类型(但不能是列表,集合,字典,可以是元组) 集 合 是 一 个 无 序 不 重 复 元素 的 集 . 基 本 功 能 包 括 关 系 测 试 和 消 除 重 复 元 素 . 集 合 对 象 还 支 持 union( 联 合),intersection(交),difference(差)和 sysmmetric difference(对称差集)等数学运算. 大括号或 s

  • python 集合 并集、交集 Series list set 转换的实例

    set转成list方法如下: list转成set方法如下: s = set('12342212')                                                      l = ['12342212']  print s    # set(['1', '3', '2', '4'])                                    s = set(l[0])  l = list(s)                             

  • Python set集合类型操作总结

    Python中除了字典,列表,元组还有一个非常好用的数据结构,那就是set了,灵活的运用set可以减去不少的操作(虽然set可以用列表代替) 小例子 1.如果我要在许多列表中找出相同的项,那么用集合是最好不过的了,用集合只用一行就可以解决 复制代码 代码如下: x & y & z # 交集 2.去重 复制代码 代码如下: >>> lst = [1,2,3,4,1] >>> print list(set(lst)) [1, 2, 3, 4] 用法 注意se

  • 跟老齐学Python之集合(set)

    回顾一下已经了解的数据类型:int/str/bool/list/dict/tuple 还真的不少了. 不过,python是一个发展的语言,没准以后还出别的呢.看官可能有疑问了,出了这么多的数据类型,我也记不住呀,特别是里面还有不少方法. 不要担心记不住,你只要记住爱因斯坦说的就好了. 爱因斯坦在美国演讲,有人问:"你可记得声音的速度是多少?你如何记下许多东西?" 爱因斯坦轻松答道:"声音的速度是多少,我必须查辞典才能回答.因为我从来不记在辞典上已经印着的东西,我的记忆力是用来

  • Python中集合类型（set）学习小结

    set 是一个无序的元素集合,支持并.交.差及对称差等数学运算, 但由于 set 不记录元素位置,因此不支持索引.分片等类序列的操作. 初始化 复制代码 代码如下: s0 = set() d0 = {} s1 = {0} s2 = {i % 2 for i in range(10)} s = set('hi') t = set(['h', 'e', 'l', 'l', 'o']) print(s0, s1, s2, s, t, type(d0)) 运行结果: 复制代码 代码如下: set() {

  • python把转列表为集合的方法

    set()函数创建一个无序不重复元素集,可进行关系测试,删除重复数据,还可以计算交集.差集.并集等. set 语法: class set([iterable]) 参数说明: iterable -- 可迭代对象对象: 返回值: 返回新的集合对象. 将列表转为集合: list1=[1,3,4,3,2,1] list1=set(list1) print(list1) 结果如下: (1,2,3,4) 扩展举例: python将3X4的矩阵列表转换为4X3列表 matrix = [ [1, 2, 3, 4

  • Python通过递归遍历出集合中所有元素的方法

    本文实例讲述了Python通过递归遍历出集合中所有元素的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: '''''通过递归遍历出集合中的所有元素 Created on 2013-9-29 @author: L.Eric '''  def print_List(list_nums):      for each_item in list_nums :           if isinstance(each_item,list):              print_Lis

  • Python实现求一个集合所有子集的示例

    方法一:回归实现 def PowerSetsRecursive(items): """Use recursive call to return all subsets of items, include empty set""" if len(items) == 0: #if the lsit is empty, return the empty list return [[]] subsets = [] first_elt = items[0]

  • Python中的集合类型知识讲解

    Python中的集合类型知识讲解

    集合类型         数学上,,把set称做由不同的元素组成的集合,集合(set)的成员通常被称做集合元素(set elements).Python把这个概念引入到它的集合类型对象里.集合对象是一组无序排列的可哈希的值,集合成员可以做字典中的键.数学集合转为Python的集合对象很有效,集合关系测试和union.intersection等操作符在Python里也同样如我们所预想地那样工作.         和其他容器类型一样,集合支持用in和not in操作符检查成员,由len()内建函数得

  • python利用递归方法实现求集合的幂集

    什么是集合的幂集? 就是原集合中所有的子集(bai包括全集du和空集)构成的集族.可数集是zhi最小的无限集: 它的幂集和实数dao集一一对应(也称同势),是不可数集. 不是所有不可数集都和实数集等势,集合的势可以无限的大.如实数集的幂集也是不可数集,但它的势比实数集大. 设X是一个有限集,|X| = k,则X的幂集的势为2的k次方. 代码 def powSet(S): #创建列表a存储S中的元素 a=[] for i in S: a.append(i) #判断S中是否只有一个元素,作为递归的终

  • Python实现利用最大公约数求三个正整数的最小公倍数示例

    本文实例讲述了Python实现利用最大公约数求三个正整数的最小公倍数.分享给大家供大家参考,具体如下: 在求解两个数的小公倍数的方法时,假设两个正整数分别为a.b的最小公倍数为d,最大公约数为c.存在这样的关系d=a*b/c.通过这个关系式,我们可以快速的求出三个正整数的最小公倍数. def divisor(a,b): c = a%b while c>0: a=b b=c c=a%b return b x1 = input("input1:") x2 = input("

  • python利用while求100内的整数和方式

    目录 1.1到100的和 2.1到100内的偶数和 3.1到100内的奇数和 1.1到100的和 定义2个变量i和sum,初值都为1,i的值每次增加1,取到100后结束程序,sum的值等于自身再加上i的值.这样i从2取到100,并且每次都与sum相加. #!/usr/bin/env python #-*- coding:utf-8 -*- i=1 sum=1 while True: i+=1 sum=sum+i if i==100: break print(sum) 2.1到100内的偶数和 方

  • Python利用redis-py实现集合与有序集合的常用指令操作

    Python利用redis-py实现集合与有序集合的常用指令操作

    目录 集合数据类型的添加操作 集合数据类型的删除元素操作 获取集合数据类型的所有元素 有序集合数据类型的添加操作 有序集合数据类型的分数值增加操作 有序集合数据类型的排序指令(降序) 集合与有序集合相关指令演示小案例 集合数据类型的添加操作 在 “redis-py” 中也是通过 “sadd” 这条指令去创建添加集合数据类型的,这一点与在 “redis” 中是一致的.示例如下: con.sadd("JobNumber", 1001, 1002, 1003) # 这里的 con 就是创建的

  • Python利用逻辑回归模型解决MNIST手写数字识别问题详解

    Python利用逻辑回归模型解决MNIST手写数字识别问题详解

    本文实例讲述了Python利用逻辑回归模型解决MNIST手写数字识别问题.分享给大家供大家参考,具体如下: 1.MNIST手写识别问题 MNIST手写数字识别问题:输入黑白的手写阿拉伯数字,通过机器学习判断输入的是几.可以通过TensorFLow下载MNIST手写数据集,通过import引入MNIST数据集并进行读取,会自动从网上下载所需文件. %matplotlib inline import tensorflow as tf import tensorflow.examples.tutori

  • Python基于time模块求程序运行时间的方法

    Python基于time模块求程序运行时间的方法

    本文实例讲述了Python基于time模块求程序运行时间的方法.分享给大家供大家参考,具体如下: 要记录程序的运行时间可以利用Unix系统中,1970.1.1到现在的时间的毫秒数,这个时间戳轻松完成. 方法是程序开始的时候取一次存入一个变量,在程序结束之后取一次再存入一个变量,与程序开始的时间戳相减则可以求出. Python中取这个时间戳的方法为引入time类之后,使用time.time();就能够拿出来.也就是Java中的System.currentTimeMillis(). 由于Python

  • python利用有道翻译实现

    python利用有道翻译实现"语言翻译器"的功能实例

    实例如下: import urllib.request import urllib.parse import json while True: content = input('请输入需要翻译的内容(退出输入Q):') if content == 'Q': break else: url = 'http://fanyi.youdao.com/translate?smartresult=dict&smartresult=rule&smartresult=ugc&sessionFrom

  • python利用高阶函数实现剪枝函数

    本文为大家分享了python利用高阶函数实现剪枝函数的具体代码,供大家参考,具体内容如下 案例: 某些时候,我们想要为多个函数,添加某种功能,比如计时统计,记录日志,缓存运算结果等等 需求: 在每个函数中不需要添加完全相同的代码 如何解决? 把相同的代码抽调出来,定义成装饰器 求斐波那契数列(黄金分割数列),从数列的第3项开始,每一项都等于前两项之和 求一个共有10个台阶的楼梯,从下走到上面,一次只能迈出1~3个台阶,并且不能后退,有多少中方法? 上台阶问题逻辑整理: 每次迈出都是 1~3 个台

  • Python利用matplotlib.pyplot绘图时如何设置坐标轴刻度

    Python利用matplotlib.pyplot绘图时如何设置坐标轴刻度

    前言 matplotlib.pyplot是一些命令行风格函数的集合,使matplotlib以类似于MATLAB的方式工作.每个pyplot函数对一幅图片(figure)做一些改动:比如创建新图片,在图片创建一个新的作图区域(plotting area),在一个作图区域内画直线,给图添加标签(label)等.matplotlib.pyplot是有状态的,亦即它会保存当前图片和作图区域的状态,新的作图函数会作用在当前图片的状态基础之上. 在开始本文之前,不熟悉的朋友可以先看看这篇文章:Python

  • python 利用栈和队列模拟递归的过程

    一.递归 递归调用:一个函数,调用的自身,称为递归调用 递归函数:一个可以调用自身的函数称为递归函数 凡是循环能干的事,递归都能干 方法: 1.写出临界条件 2.找这一次和上一次的关系 3.假设当前函数已经能用,调用自身计算上一次的结果再求出本次的结果 下面我们通过两段代码简单看一下递归和非递归的区别: 输入一个大于等于1的数,求1到n的和! # 普通函数方法 def hanshu(n): sum = 0 # 循环遍历每一个数字,将他们加到一个事先定义好的变量上,直到加完 for x in ra

随机推荐