【Python】再帰を使って文字列のすべての順列を辞書式順序で出力する方法

文字列のすべての順列を辞書式順序（辞書順）で出力したい場合、再帰を活用したアプローチが有効です。具体的には、要素の並びを「for」ループで反復処理しながら、「join」メソッドを使って各要素を連結し、文字列として出力するメソッドを定義します。

以下に、実際の実装例を示します。

サンプルコード

from math import factorial
def lexicographic_permutation_order(s):
    my_sequence = list(s)
    for _ in range(factorial(len(my_sequence))):
        print(''.join(my_sequence))
        next = next_in_permutation(my_sequence)

        if next is None:
            my_sequence.reverse()
        else:
            my_sequence = next

def next_in_permutation(my_sequence):
    if len(my_sequence) == 0:
        return None
    next = next_in_permutation(my_sequence[1:])
    if next is None:
        my_sequence[1:] = reversed(my_sequence[1:])
        q = 1
        while q < len(my_sequence) and my_sequence[0] > my_sequence[q]:
            q += 1
        if q == len(my_sequence):
            return None
        my_sequence[0], my_sequence[q] = my_sequence[q], my_sequence[0]
        return my_sequence
    else:
        return [my_sequence[0]] + next

my_input = input('Enter a string : ')
print("The string is :")
print(my_input)
print("The method is being called...")
lexicographic_permutation_order(my_input)

実行結果

Enter a string : hey
The string is :
hey
The method is being called...
hey
hye
yeh
yhe
hey
hye

コードの解説

• まず、必要なモジュール（math.factorial）をインポートします。これは文字列の長さから順列の総数を求めるために使用されます。

• lexicographic_permutation_order というメソッドを定義します。このメソッドは、文字列をリストに変換したうえで、階乗の回数だけ反復処理を行い、現在の並びを出力しながら次の順列を生成していきます。

• next_in_permutation メソッドは、再帰的に呼び出されることで、現在の並びから次の順列を決定します。末尾部分が降順になっている場合はそれを反転し、適切な位置にある要素を入れ替えることで、次の順列を作り出します。

• ユーザーから文字列を入力として受け取り、その内容をコンソールに表示します。

• 入力された文字列を引数として渡し、メソッドを呼び出します。

• 生成されたすべての順列がコンソールに出力されます。

ポイント

このアルゴリズムは「次の順列を生成する」手法（ネクスト・パーミュテーション）に基づいています。n 文字の文字列に対する順列の総数は n!（階乗）となるため、math.factorial を使ってループの回数を決定しています。また、処理の一部を再帰的な構造にすることで、コードを簡潔に保ちながら順列の生成ロジックを実現している点も特徴です。