Pythonでセットのすべての順列を生成する3つの方法

数学において、集合のすべての要素を何らかの順序や並びに配置すること、また、すでに順序付けられた集合の要素を並べ替えることを順列（パーミュテーション）と呼びます。

Pythonでは、いくつかの異なる手法を使って順列を生成できます。本記事では、代表的な3つの方法をコード例とともにわかりやすく紹介します。

方法1：itertoolsモジュールを使う

Pythonには、順列や組み合わせを扱うための専用モジュール itertools が標準で用意されています。最もシンプルで推奨される方法です。

モジュールのインポート

>>> import itertools
>>>

permutations関数で順列を生成

permutations 関数を使うと、リスト内のN個の値からなる順列（順序が重要な場合）を取得できます。例えば、[1, 2, 3, 4] から2個（N=2）を選ぶ場合は以下のように記述します。

順列（順序が重要）:
>>> print(list(itertools.permutations([1,2,3,4], 2)))
[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

combinations関数で組み合わせを生成

一方、順序が重要でない場合は combinations 関数を使用します。

>>> print(list(itertools.combinations('1234', 2)))
[('1', '2'), ('1', '3'), ('1', '4'), ('2', '3'), ('2', '4'), ('3', '4')]

方法2：中間リストを作らないジェネレータ実装

次に、新しい中間リストを作成せずにリストの順列を生成する実装例を示します。ジェネレータ（yield）を活用することで、メモリ効率の良い処理が可能になります。

def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p
        for i in range(low + 1, len(xs)):
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p
            xs[low], xs[i] = xs[i], xs[low]

for p in permute([1, 2, 3]):
    print(p)

出力結果

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

方法3：再帰を使った実装

最後に、再帰呼び出しを利用した順列生成の実装例です。copy モジュールを使ってプレフィックス（先頭部分）と残りの要素を管理しながら、再帰的に順列を構築していきます。

import copy

def perm(prefix, rest):
    for e in rest:
        new_rest = copy.copy(rest)
        new_prefix = copy.copy(prefix)
        new_prefix.append(e)
        new_rest.remove(e)
        if len(new_rest) == 0:
            print(new_prefix + new_rest)
            continue
        perm(new_prefix, new_rest)

perm([], [1, 2, 3])

出力結果

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

まとめ

日常的な用途では、標準ライブラリの itertools.permutations を使うのが最も簡単で確実です。一方、アルゴリズムの学習やメモリ効率・柔軟性といった特殊な要件がある場合には、ジェネレータや再帰による自前実装も有効な選択肢となります。目的に応じて最適な方法を選びましょう。