指定された文字列のすべての順列を出力するPythonプログラム

本記事では、以下の問題に対する解決策について詳しく学んでいきます。

問題文

1つの文字列が与えられたとき、その文字列から作成できるすべての順列（並べ替えの組み合わせ）を表示する必要があります。

それでは、以下の実装例で具体的な解決策を見ていきましょう。

実装例

# リストを文字列に変換
def toString(List):
    return ''.join(List)

# 順列の生成
def permute(a, l, r):
    if l == r:
        print(toString(a))
    else:
        for i in range(l, r + 1):
            a[l], a[i] = a[i], a[l]
            permute(a, l + 1, r)
            a[l], a[i] = a[i], a[l]  # バックトラッキング

# メイン処理
string = "TUT"
n = len(string)
a = list(string)
print("The possible permutations are:", end="\n")
permute(a, 0, n-1)

出力

The possible permutations are:
TUT
TTU
UTT
UTT
TUT
TTU

アルゴリズムの解説

このプログラムでは、バックトラッキング（探索の巻き戻し）と呼ばれる手法を用いて順列を生成しています。処理の流れは以下の通りです。

まず、文字列をリストに変換します。次に、再帰関数 permute の中で、左端の位置とそれ以降の各位置にある文字を順番に入れ替えながら、すべての組み合わせを試していきます。各再帰呼び出しが終わった後に文字の入れ替えを元に戻す（バックトラック）ことで、次の候補を正しく生成できる仕組みです。

なお、すべての変数はローカルスコープ内で宣言されており、それぞれの参照関係は上図のようになっています。

また、入力文字列に重複した文字が含まれている場合（この例では「T」が2つ）、同じ並びの結果が複数回出力される点に注意してください。重複を排除したい場合は、結果をセット（set）に格納するなどの工夫が必要です。

itertoolsを使った代替手法

Pythonの標準ライブラリ itertools.permutations を使えば、より簡潔に同じ結果を得ることもできます。

from itertools import permutations

string = "TUT"
for p in permutations(string):
    print(''.join(p))

まとめ

本記事では、Pythonを使って指定された文字列のすべての順列を出力するプログラムの作成方法について学びました。バックトラッキングを活用した再帰的なアプローチは、順列生成の基本的かつ重要なテクニックです。ぜひ実際にコードを動かして、挙動を確認してみてください。