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

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

問題の概要

あるセットと整数 n が与えられたとき、要素数がちょうど n 個になる部分集合をすべて求めて表示します。

この問題は、Pythonの標準ライブラリ itertools に含まれる combinations() 関数を使うことで簡潔に解決できます。この関数は、イテラブルから長さ r の組み合わせをすべて列挙してくれるため、部分集合の生成に最適です。また、セットには重複した要素が格納されないため、重複を含むリテラルからセットを作成しても、自動的に一意な要素だけが扱われます。

例1：combinations() の基本的な使い方

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

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

# ドライバーコード
s = {'t', 'u', 't', 'o', 'r'}
n = 2
print(find_subsets(s, n))

出力

[('u', 'r'), ('u', 'o'), ('u', 't'), ('r', 'o'), ('r', 't'), ('o', 't')]

この例では、重複する 't' が取り除かれた4つの要素から2つを選ぶ組み合わせ、つまり6通りの部分集合がタプルのリストとして返されます。セットは順序を保持しないため、実行環境によって出力の並び順が異なる場合があります。

例2：map() で各組み合わせをセットに変換する

# itertools の combinations 関数を使用
from itertools import combinations

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

s = {'t', 'u', 't', 'o', 'r'}
n = 3
print(find_subsets(s, n))

出力

[{'u', 'o', 'r'}, {'u', 'r', 't'}, {'u', 'o', 't'}, {'o', 'r', 't'}]

map(set, ...) を使うことで、各組み合わせ（タプル）を個別のセットへ変換でき、結果として「セットのリスト」を取得できます。4つの要素から3つを選ぶため、4通りの部分集合が生成されます。

例3：リスト内包表記でセットのリストを作成する

# combinations とリスト内包表記を組み合わせる
from itertools import combinations

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

s = {'t', 'u', 't', 'o', 'r'}
n = 3
print(find_subsets(s, n))

出力

[{'u', 'o', 'r'}, {'u', 'r', 't'}, {'u', 'o', 't'}, {'o', 'r', 't'}]

リスト内包表記を活用すると、より読みやすく簡潔なコードになります。いずれの変数も関数のローカルスコープ内で宣言されており、外部の状態に依存しない独立した関数として動作します。

まとめ

この記事では、itertools.combinations() を活用して、セットから指定サイズのすべての部分集合を取得する3つのアプローチ（タプルのリスト、map() による変換、リスト内包表記）を学びました。生成される組み合わせの総数は二項係数 C(要素数, n) で決まるため、大きなセットを扱う場合は計算量やメモリ使用量に注意してください。