在 Python 中查詢 Powerset
Hemank Mehtani
2023年1月30日
- 在 Python 中使用迭代方法獲取 Powerset
-
在 Python 中使用
itertools.combinations函式查詢冪集 - 在 Python 中使用列表推導式查詢冪集
- 在 Python 中使用遞迴方法查詢冪集
在數學中，任何集合的冪集是一個包含給定集合的所有可能子集以及一個空集的集合。換句話說，集合的所有子集也稱為冪集。在 Python 中可以有一個強大的列表、集合、字串等集合。
在本教程中，我們將在 Python 中找到給定集合的冪集。
在 Python 中使用迭代方法獲取 Powerset
雖然我們可以同時使用遞迴方法和迭代方法來找到冪集，但迭代方法比遞迴方法更受歡迎，因為它的過程更快。
我們使用巢狀的 for 迴圈來建立這樣的冪集。
例如，
def powerset(fullset):
listsub = list(fullset)
subsets = []
for i in range(2 ** len(listsub)):
subset = []
for k in range(len(listsub)):
if i & 1 << k:
subset.append(listsub[k])
subsets.append(subset)
return subsets
subsets = powerset(set([1, 2, 3, 4]))
print(subsets)
print(len(subsets))
輸出：
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]
16
在 Python 中使用 itertools.combinations 函式查詢冪集
itertools 是 Python 中的一個模組，用於迭代資料結構。這些資料結構也稱為可迭代物件。可以使用 for 迴圈跳過它們。
這個模組的 combinations 函式可以建立一個集合的組合來建立一個 powerset。
請參考下面的程式碼。
from itertools import combinations
def powerset(string):
n = len(string)
for i in range(0, n + 1):
for element in combinations(string, i):
print("".join(element))
string = ["x", "y", "z"]
powerset(string)
輸出：
x
y
z
xy
xz
yz
xyz
在 Python 中使用列表推導式查詢冪集
列表推導式是一種基於現有列表建立新列表的方法。它提供了更短的語法，比用於建立列表的其他函式和迴圈更緊湊、更快。
我們也在這個方法中使用了一個巢狀的 for 迴圈。
例如，
def get_subsets(fullset):
listrep = list(fullset)
n = len(listrep)
return [[listrep[k] for k in range(n) if i & 1 << k] for i in range(2 ** n)]
string = ["x", "y", "z"]
print(get_subsets(string))
輸出：
[[], ['x'], ['y'], ['x', 'y'], ['z'], ['x', 'z'], ['y', 'z'], ['x', 'y', 'z']]
在 Python 中使用遞迴方法查詢冪集
遞迴方法是一種方法，其中函式不斷使用不同的引數呼叫自身。我們可以建立一個遞迴函式來查詢集合的冪集。
例如，
def powerSet(string, index, c):
if index == len(string):
print(c)
return
powerSet(string, index + 1, c + string[index])
powerSet(string, index + 1, c)
s1 = ["a", "b", "c"]
index = 0
c = ""
powerSet(s1, index, c)
輸出：
abc
ab
ac
a
bc
b
c