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

时间:2020-9-7 作者:admin


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

代码

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)次重复,但是它可以考虑到所有情况。

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。