Python で Powerset を探す
Hemank Mehtani
2023年1月30日
- Python で反復アプローチを使用してパワーセットを取得する
-
Python で
itertools.combinations関数を使用してべき集合を検索する - Python でリスト内包法を使用してべき集合を見つける
- Python で再帰的方法を使用してべき集合を見つける
数学では、任意のセットのべき集合は、空のセットとともに、特定のセットのすべての可能なサブセットを含むセットです。言い換えると、セットのすべてのサブセットは、べき集合とも呼ばれます。Python には、リスト、セット、文字列などのべき集合が存在する可能性があります。
このチュートリアルでは、Python で特定のセットのべき集合を見つけます。
Python で反復アプローチを使用してパワーセットを取得する
再帰的アプローチと反復的アプローチの両方を使用してパワーセットを見つけることができますが、プロセスが高速であるため、再帰的アプローチよりも反復的アプローチの方が適しています。
ネストされた 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 関数は、セットの組み合わせを作成してパワーセットを作成できます。
以下のコードを参照してください。
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