Pythonでセットから指定したサイズのすべての部分集合を取得する方法

この記事では、Pythonを使ってセット（集合）から指定したサイズ n のすべての部分集合（サブセット）を取得する方法について解説します。

問題文

問題：あるセットが与えられたとき、その中からサイズ n のすべての部分集合を列挙する必要があります。

この問題は、Pythonの標準ライブラリである itertools を活用することで、複数の方法で解決できます。ここでは代表的な3つのアプローチを順番に紹介します。

方法1：itertools.combinations() メソッドを使う

itertools.combinations() は、イテラブルから指定した長さのすべての組み合わせをタプルとして生成する関数です。結果をリストに変換して返します。

# itertoolsモジュールをインポート
import itertools

def findsubsets(s, n):
    return list(itertools.combinations(s, n))

# メイン処理
s = {1, 2, 3, 4, 5}
n = 4
print(findsubsets(s, n))

出力結果

[(1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 4, 5), (1, 3, 4, 5), (2, 3, 4, 5)]

この方法では、各部分集合がタプルとして返される点に注意してください。

方法2：map() と combinations() を組み合わせる

map() 関数と set を組み合わせることで、生成された各組み合わせをセット型に変換して返すことができます。

# itertoolsモジュールからcombinationsをインポート
from itertools import combinations

def findsubsets(s, n):
    return list(map(set, itertools.combinations(s, n)))

# ドライバーコード
s = {1, 2, 3, 4, 5}
n = 4
print(findsubsets(s, n))

出力結果

[{1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}]

この方法では、各部分集合がセット型として返されます。

方法3：リスト内包表記を使う

リスト内包表記を使えば、より簡潔で読みやすいコードで同じ結果を得ることができます。Pythonicな書き方として推奨されるスタイルです。

# itertoolsモジュールをインポート
import itertools

def findsubsets(s, n):
    return [set(i) for i in itertools.combinations(s, n)]

# ドライバーコード
s = {1, 2, 3, 4, 5}
n = 4
print(findsubsets(s, n))

出力結果

[{1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}]

まとめ

この記事では、itertools.combinations() を活用して、セットから指定したサイズのすべての部分集合を取得する3つの方法を紹介しました。タプルのまま扱いたい場合は方法1、セット型として扱いたい場合は方法2または方法3が便利です。用途に応じて最適な方法を選択してください。