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è)X是一個(gè)有限集，|X| = k，則X的冪集的勢為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之自動(dòng)獲取公網(wǎng)IP的實(shí)例講解
下面小編就為大家?guī)硪黄狿ython之自動(dòng)獲取公網(wǎng)IP的實(shí)例講解。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-10-10
淺談Python從全局與局部變量到裝飾器的相關(guān)知識(shí)
今天給大家?guī)淼氖顷P(guān)于Python的相關(guān)知識(shí),文章圍繞著Python從全局與局部變量到裝飾器的相關(guān)知識(shí)展開,文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下2021-06-06
淺談keras 模型用于預(yù)測時(shí)的注意事項(xiàng)
這篇文章主要介紹了淺談keras 模型用于預(yù)測時(shí)的注意事項(xiàng)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-06-06
淺談python 四種數(shù)值類型(int,long,float,complex)
下面小編就為大家?guī)硪黄獪\談python 四種數(shù)值類型(int,long,float,complex)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-06-06
Python鏈?zhǔn)秸{(diào)用數(shù)據(jù)處理實(shí)際應(yīng)用實(shí)例探究
本文將深入介紹Python鏈?zhǔn)秸{(diào)用的概念、原理以及實(shí)際應(yīng)用,通過豐富的示例代碼,幫助讀者更全面地理解和應(yīng)用這一編程技巧2024-01-01
python+selenium爬取微博熱搜存入Mysql的實(shí)現(xiàn)方法
這篇文章主要介紹了python+selenium爬取微博熱搜存入Mysql的實(shí)現(xiàn)方法,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-01-01
xpath是最常用且最便捷高效的一種解析方式，通用型強(qiáng)，其不僅可以用于python語言中，還可以用于其他語言中，數(shù)據(jù)解析建議首先xpath2021-09-09
python自動(dòng)12306搶票軟件實(shí)現(xiàn)代碼
這篇文章主要為大家詳細(xì)介紹了python自動(dòng)12306搶票軟件的實(shí)現(xiàn)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02
python實(shí)現(xiàn)網(wǎng)站的模擬登錄
這篇文章主要介紹了python實(shí)現(xiàn)網(wǎng)站的模擬登錄的相關(guān)資料，通過自己構(gòu)造post數(shù)據(jù)來用Python實(shí)現(xiàn)登錄過程,需要的朋友可以參考下2016-01-01
Python中魔法參數(shù)?*args?和?**kwargs使用詳細(xì)講解
這篇文章主要介紹了Python中魔法參數(shù)?*args?和?**kwargs使用的相關(guān)資料,*args和**kwargs是Python中實(shí)現(xiàn)函數(shù)參數(shù)可變性的重要工具,分別用于接受任意數(shù)量的位置參數(shù)和關(guān)鍵字參數(shù),文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-12-12