python利用遞歸方法實現(xiàn)求集合的冪集
什么是集合的冪集?
就是原集合中所有的子集（bai包括全集du和空集）構(gòu)成的集族?？蓴?shù)集是zhi最小的無限集； 它的冪集和實數(shù)dao集一一對應(yīng)（也稱同勢），是不可數(shù)集。
不是所有不可數(shù)集都和實數(shù)集等勢，集合的勢可以無限的大。如實數(shù)集的冪集也是不可數(shù)集，但它的勢比實數(shù)集大。 設(shè)X是一個有限集，|X| = k，則X的冪集的勢為2的k次方。
代碼
def powSet(S):
#創(chuàng)建列表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))
#結(jié)果
{{frozenset({2}), frozenset({2, 3}), frozenset({1, 2}), frozenset({1, 2, 3}), frozenset({3}), frozenset({1}), frozenset(), frozenset({1, 3})}}
需要知識
冪集的概念
python set 和 frozenset 數(shù)據(jù)類型
心得體會
筆者在寫代碼時遇到的問題是認為powSet(S-1)（S-1代表S中去掉任一個元素）就完完全全地替代了真正去掉那一個隨機元素的元素組成的冪集。
實際上這樣是不完全的，因為設(shè)置的遞歸規(guī)則有缺陷，不可能完全遍歷所有情況。
解決：借助于集合元素的不可重復(fù)添加這一特性，我們可以遍歷遍歷所有S中的元素，都讓它們進行一次遞歸操作，這樣做雖然會產(chǎn)生n(S)次重復(fù)，但是它可以考慮到所有情況。
到此這篇關(guān)于python利用遞歸方法實現(xiàn)求集合的冪集的文章就介紹到這了,更多相關(guān)python遞歸方法求集合的冪集內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
通過python讀取txt文件和繪制柱形圖的實現(xiàn)代碼
這篇文章主要介紹了通過python讀取txt文件和繪制柱形圖的實現(xiàn)代碼,代碼簡單易懂，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-03-03
Python使用pickle模塊實現(xiàn)序列化功能示例
這篇文章主要介紹了Python使用pickle模塊實現(xiàn)序列化功能,結(jié)合實例形式分析了基于pickle模塊的序列化操作相關(guān)操作技巧,需要的朋友可以參考下2018-07-07
這篇文章主要介紹了python使用json序列化datetime類型實例解析，分享了相關(guān)代碼示例，小編覺得還是挺不錯的，具有一定借鑒價值，需要的朋友可以參考下2018-02-02
Python基于動態(tài)規(guī)劃算法解決01背包問題實例
這篇文章主要介紹了Python基于動態(tài)規(guī)劃算法解決01背包問題,結(jié)合實例形式分析了Python動態(tài)規(guī)劃算法解決01背包問題的原理與具體實現(xiàn)技巧,需要的朋友可以參考下2017-12-12
Python數(shù)據(jù)結(jié)構(gòu)之雙向鏈表詳解
單鏈表只有一個指向直接后繼的指針來表示結(jié)點間的邏輯關(guān)系，可以方便的從任一結(jié)點開始查找其后繼結(jié)點，但要找前驅(qū)結(jié)點則比較困難，雙向鏈表是為了解決這一問題，使用兩個指針表示結(jié)點間的邏輯關(guān)系。本文將重點為大家介紹雙向鏈表的相關(guān)操作，需要的可以參考一下2022-01-01
Python django使用多進程連接mysql錯誤的解決方法
這篇文章主要介紹了Python django使用多進程連接mysql錯誤的解決方法，詳細的介紹了解決方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-10-10
今天小編就為大家分享一篇python如何保證輸入鍵入數(shù)字的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-08-08
在Python的Flask框架中驗證注冊用戶的Email的方法
這篇文章主要介紹了在Python的Flask框架中驗證注冊用戶的Email的方法,包括非常詳細的測試過程,極力推薦!需要的朋友可以參考下2015-09-09
Python虛擬環(huán)境的創(chuàng)建和包下載過程分析
這篇文章主要介紹了Python虛擬環(huán)境的創(chuàng)建和包下載，本文通過實例給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-06-06
今天小編就為大家分享一篇關(guān)于Python判斷對象是否相等及eq函數(shù)的講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-02-02