Python でリストのすべての順列を生成する方法

Python の標準ライブラリを使うと、リストの順列を生成できます。処理を独自に組み立てたい場合は、再帰または反復処理によるアルゴリズムも選べます。順列とは、選んだ要素を並べたものです。組み合わせとは異なり、順序も区別します。結果の数は階乗的に増えるため、すべての並びを生成できるのは、入力が比較的小さい場合に限られます。

itertools ライブラリを使う

多くの場合は itertools.permutations を使うのが簡単です。この関数はタプルのイテレーターを返すため、結果をすぐにリストへ格納せず、1つずつ処理できます。既定では r に入力の長さが設定され、各結果にすべての要素が含まれます。次の例では r=2 によって順序付きのペアを生成し、ループでは長さ1から3までの順列を生成します。

リスト [1, 2, 3] を使うと、プログラムは次のように出力します。

from itertools import permutations

data = [1, 2, 3]
print("full:", list(permutations(data)))
print("length 2:", list(permutations(data, r=2)))
print("lengths 1 to 3:")
for r in range(1, len(data) + 1):
    print(r, list(permutations(data, r)))

full: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
length 2: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
lengths 1 to 3:
1 [(1,), (2,), (3,)]
2 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
3 [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

引数 r は各タプルに含める要素数を指定します。空でないすべての長さの順列を生成するには、上の例のように r を1から入力の長さまで変えて関数を呼び出します。itertools.permutations は値そのものではなく要素の位置を基準にするため、入力に同じ値が複数あると、同じタプルが結果に重複して現れることがあります。

関数の完全なシグネチャと動作については、公式の itertools ドキュメントを参照してください。

再帰関数で順列を生成する

再帰による方法では、要素を1つずつ選び、残りの要素の各順列の先頭にその要素を置きます。基底条件では、空の並びを1つ含むリストを返します。この条件により、入力が空の場合も含め、どの長さの入力でも処理できます。この実装はリストを返すため、構築方法を学んだり、独自に変更したりしたい場合に役立ちます。

def permute(data):
    if not data:
        return [[]]

    result = []
    for index, item in enumerate(data):
        remaining = data[:index] + data[index + 1:]
        for tail in permute(remaining):
            result.append([item] + tail)
    return result

print(permute([1, 2, 3]))

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

再帰呼び出しのたびに1つの位置を取り除くため、基底条件に達するまで入力は小さくなります。異なる位置に同じ値がある場合、同じリストが複数回生成されることがあります。この実装は再帰呼び出しを多数行い、結果全体をメモリに保持します。そのため、学習や小さな入力に向いています。独自の構築方法が不要なら、標準ライブラリのイテレーターを使うとよいでしょう。

反復処理で順列を生成する

すでに集めた部分的な並びのすべての位置に、新しい要素を挿入して結果を作る方法もあります。最初は空の並びを1つだけ用意し、処理を進めるたびに、次の入力要素の個数分だけ結果が増えます。この方法では再帰呼び出しを避けられますが、それでも結果全体を保存します。

def iterative_permute(data):
    results = [[]]
    for item in data:
        next_results = []
        for ordering in results:
            for index in range(len(ordering) + 1):
                next_results.append(ordering[:index] + [item] + ordering[index:])
        results = next_results
    return results

print(iterative_permute([1, 2, 3]))

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

挿入する順番によって、結果が返される順序は変わりますが、生成される順列の種類は変わりません。この手順に沿った構築が用途に合う場合に選び、結果をすべて保持するためのメモリも考慮してください。

まとめ

簡潔な遅延評価のイテレーターが必要なら itertools.permutations を使い、特定の長さだけが必要な場合は r を指定します。構築方法を学んだり、独自に調整したりする場合は、再帰または反復的な挿入方法を選べます。位置が異なる長さ n のリストには、全要素を使う順列が n! 個あります。そのため、処理時間も、結果を実体化したときの保存容量も急速に増加します。大きな入力では、必要に応じてイテレーターから順次処理するか、対象の長さや要素の選び方を絞ってください。

よくある質問

1. 順列とは何ですか？
   要素を順序付きで選んだものです。たとえば [1, 2] と [2, 1] は、順序が異なるため別の順列です。

2. itertools.permutations はどのように動作しますか？
   入力のイテラブルから、長さ r のタプルを順に返します。r を省略すると、入力全体の長さが使われます。関数は結果を遅延生成しますが、イテレーターをリストに変換すると、すべての結果が保存されます。

3. 入力に同じ値が含まれているとどうなりますか？
   この関数は値の同一性ではなく、要素の位置を基準に処理します。そのため、同じ値が入力にあると、内容が同じタプルが生成されることがあります。結果をすべてセットに変換すれば、要素がハッシュ可能な場合は生成後に重複タプルを取り除けますが、重複の生成自体は避けられません。重複処理を避けるには、各段階で同じ値の選択をスキップするアルゴリズムを使います。

4. 順列はいくつありますか？
   異なる n 個の位置から全要素を使う順列は n! 個です。r 個だけを選ぶ場合は n! / (n - r)! 個です。

5. 入力はどのくらいの大きさまで扱えますか？
   どの環境や用途にも当てはまる一律の上限はありません。順列の数は階乗的に増えるため、中程度の入力でも処理に時間がかかることがあり、すべてを保存するには大きなメモリが必要です。全要素を使う順列を一度にすべて必要としない場合は、遅延評価のイテレーターを使うか、r を小さくしてください。