Pythonで文字列のすべての順列を取得する方法【itertoolsと再帰で解説】

itertools.permutationsを使った方法

Pythonで文字列のすべての順列（並べ替え）を求める最も簡単な方法は、標準ライブラリのitertoolsモジュールにあるpermutations()関数を使用することです。この関数は、イテラブルなオブジェクトから要素を取り出し、指定した長さrの順列をタプルとして順番に返します。

結果を文字列として取得するには、関数の戻り値をループで処理し、各タプルの要素をjoin()で連結します。以下に具体例を示します。

from itertools import permutations

result = [''.join(p) for p in permutations('dune')]
print(result)

実行すると、「dune」の4文字から作られる全24通りの並べ替えがリストとして出力されます。

['dune', 'duen', 'dnue', 'dneu', 'deun', 'denu',
 'udne', 'uden', 'unde', 'uned', 'uedn', 'uend',
 'ndue', 'ndeu', 'nude', 'nued', 'nedu', 'neud',
 'edun', 'ednu', 'eudn', 'eund', 'endu', 'enud']

再帰を使って自作する方法

標準ライブラリに頼らず、自分でアルゴリズムを実装したい場合は、再帰的なアプローチが有効です。以下のコードでは、現在のステップ位置とそれ以降の各位置の文字を入れ替えながら、再帰的にすべての組み合わせを生成しています。

def permutations(string, step=0):
    if step == len(string):
        # 文字列の末尾に到達したら、完成した順列を出力
        print(''.join(string))
    for i in range(step, len(string)):
        # 文字列をコピーしてリストとして保持
        string_copy = [c for c in string]
        # 現在のインデックスiとstepの位置にある文字を入れ替える
        string_copy[step], string_copy[i] = string_copy[i], string_copy[step]
        # まだ入れ替えていない部分に対して再帰的に処理
        permutations(string_copy, step + 1)

permutations('one')

実行結果：

one
oen
noe
neo
eno
eon

注意点：Noneが出力される問題

元のコードではprint(permutations('one'))のように関数呼び出しをprint()で囲んでいました。しかし、この関数は内部で結果を出力する仕様のため、戻り値はNoneとなり、余計な「None」が画面に表示されてしまいます。関数自体が結果を出力する場合は、呼び出し時にprint()で囲む必要がない点に注意しましょう。