反復法を使って文字列のすべての順列を生成する方法

この記事では、文字列のすべての順列（パーミュテーション）を求める方法を解説します。順列の生成には一般的に再帰呼び出しとバックトラッキングを組み合わせた手法がよく知られていますが、ここでは反復（イテレーション）のみを用いたアプローチを紹介します。

たとえば、文字列「ABC」のすべての順列は {ABC, ACB, BAC, BCA, CAB, CBA} の6通りです。処理の流れを正確に理解するために、まずアルゴリズムから見ていきましょう。

アルゴリズム

getAllPerm(str)

begin
   文字列の文字を昇順にソートする
   while true, do
      現在の文字列 str を表示する
      i := str の長さ – 1
      while str[i - 1] >= str[i], do
         i := i – 1
         if i が 0 ならば
            return（すべての順列を生成済み）
         end if
      done
      j := str の長さ – 1
      while j > i AND str[j] <= str[i – 1], do
         j := j – 1
      done
      str[i - 1] と str[j] の文字を交換する
      i 以降の部分文字列を反転する
   done
end

アルゴリズムのポイント

この手法は「次の順列（next permutation）」を辞書順に毎回求めていくという考え方に基づいています。処理の手順を整理すると以下のようになります。

1. 最初に文字列をソートし、辞書順で最小の並びから開始できるようにします。
2. 後ろから走査して、「str[i-1] < str[i]」となる境界位置（ピボット）i を探します。見つからなければ、すべての順列を出力し終えたことになるため終了します。
3. ピボットより右側で、str[i-1] より大きい文字の中で最も右にあるもの（位置 j）を見つけます。
4. str[i-1] と str[j] を交換し、i 以降の部分を反転させます。これにより「次の順列」が得られます。

この操作を繰り返すことで、重複なく辞書順にすべての順列を生成できます。C++標準ライブラリの std::next_permutation も同様の原理で動作しています。

C++での実装例

#include <iostream>
#include <algorithm>
using namespace std;
void getAllPerm(string str){
   sort(str.begin(), str.end());
   while (true){
      cout << str << endl;
      int i = str.length() - 1;
      while (str[i-1] >= str[i]){
         if (--i == 0)
         return;
      }
      int j = str.length() - 1;
      while (j > i && str[j] <= str[i - 1])
      j--;
      swap(str[i - 1], str[j]);
      reverse (str.begin() + i, str.end());
   }
}
int main(){
   string str = "WXYZ";
   getAllPerm(str);
}

出力結果

文字列「WXYZ」（4文字）の場合、4! = 24通りの順列が辞書順に出力されます。

WXYZ
WXZY
WYXZ
WYZX
WZXY
WZYX
XWYZ
XWZY
XYWZ
XYZW
XZWY
XZYW
YWXZ
YWZX
YXWZ
YXZW
YZWX
YZXW
ZWXY
ZWYX
ZXWY
ZXYW
ZYWX
ZYXW

まとめ

再帰を使わない反復型の順列生成は、スタックオーバーフローの心配がなく、辞書順に順列を取り出せる点が大きな利点です。計算量は順列の総数 n! に比例するため、文字数が長くなると出力件数が爆発的に増える点には注意が必要ですが、アルゴリズム自体はシンプルで実用的な手法です。