【Python】再帰なしで文字列の全順列を辞書式順序に出力する方法

再帰を使わずに、文字列のすべての順列を辞書式順序（辞書順）で出力したい場合は、文字列を引数として受け取る関数を定義します。この関数では、シンプルな「for」ループで文字列の長さの階乗回数だけ反復処理を行い、「while」条件で特定の制約をチェックしながら、次の順列を順次生成していきます。

以下に具体的な実装例を示します。

サンプルコード

from math import factorial

def lex_permutation(my_string):
    for i in range(factorial(len(my_string))):
        print(''.join(my_string))
        i = len(my_string) - 1
        while i > 0 and my_string[i-1] > my_string[i]:
            i -= 1
        my_string[i:] = reversed(my_string[i:])
        if i > 0:
            q = i
            while my_string[i-1] > my_string[q]:
                q += 1
            temp_variable = my_string[i-1]
            my_string[i-1] = my_string[q]
            my_string[q] = temp_variable

my_string = 'bhd'
print("The string is ")
print(my_string)
my_string = list(my_string)
print("The string is being sorted")
my_string.sort()
lex_permutation(my_string)

実行結果

The string is 
bhd
The string is being sorted
bdh
bhd
dbh
dhb
hbd
hdb

コードの解説

• まず、mathモジュールからfactorial（階乗）をインポートします。

• 文字列を引数として受け取る「lex_permutation」という名前の関数を定義します。

• factorialメソッドを使い、文字列の長さの階乗回数だけ反復処理を行います（n文字の順列はn!個存在するためです）。

• 文字列を後ろから走査し、隣接する文字同士の大小関係を比較します。

• 条件を満たす部分を反転させ、必要に応じて文字を入れ替えることで、次の順列を生成します。

• 関数の外側で対象となる文字列を定義し、コンソールに表示します。

• 文字列をリストに変換したうえでソートします。これは、辞書式順序で最初の順列から列挙を開始するために必要な処理です。

• ソート済みの文字列を引数として関数を呼び出します。

• すべての順列が辞書式順序でコンソールに出力されます。

アルゴリズムのポイント：「次の順列（Next Permutation）」

このプログラムで使われているのは、「次の順列（next permutation）」と呼ばれる古典的なアルゴリズムです。現在の並びから、辞書式順序で「次に大きい」並びを求める操作を繰り返すことで、すべての順列を重複なく効率的に列挙できます。

大まかな流れは以下の通りです。

1. 文字列の末尾から走査し、初めて「左の文字 < 右の文字」となる位置（ピボット候補）を見つけます。
2. 見つかった位置以降の部分文字列を反転させます。
3. ピボットより左の文字と、右側の部分の中で「その文字より大きい最小の文字」を交換します。

この手順をn!回繰り返すことで、ソート済みの初期状態から始めて、すべての順列を辞書式順序どおりに得ることができます。再帰呼び出しを一切使用しないため、深いネストによるスタックオーバーフローの心配がないのも大きな利点です。