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