python利用递归方法实现求集合的幂集_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})}}