C++で実装するAlexander Bogomolnyの順列生成アルゴリズム ― 1からNまでの全順列を出力する方法

本記事では、1からNまでの自然数のすべての順列を生成するAlexander Bogomolnyの非順序順列アルゴリズム（UnOrdered Permutation Algorithm）をC++で実装する方法を解説します。このアルゴリズムは再帰呼び出しとバックトラックを組み合わせることで、N個の要素からなるすべての並べ替えパターン（N!通り）を漏れなく列挙できます。

アルゴリズムの流れ

このアルゴリズムでは、静的変数 l で現在のレベル（配置済みの要素数）を管理し、配列 Val[] の空きスロット（値が0の位置）へ順に数値を配置していきます。レベルがNに達すると1つの順列が完成して表示され、その後バックトラックしながら残りの組み合わせを探索します。

擬似コード

Begin
    function AlexanderBogomolny() を実装する
    引数:
        Val[] = 配列
        N = 入力として与える要素数
        K = 現在のレベル
    関数の処理:
        l を -1 で初期化
        l = l + 1
        Val[k] = l
        if (l == N)
            display(Val, N) を呼び出して順列を表示
        else
            for i = 0 to N-1
                if (Val[i] == 0)
                    AlexanderBogomolny(Val, N, i) を再帰呼び出し
                l = l - 1
                Val[k] = 0
End

C++による実装例

#include<iostream>
#include<iomanip>
using namespace std;

// 順列を表示するための関数
void display(const int *n, const int size) {
    int i;
    if (n != 0) {
        for (i = 0; i < size; i++) {
            cout << setw(4) << n[i];
        }
        cout << "\n";
    }
}

// Alexander Bogomolnyの順列生成アルゴリズム
void AlexanderBogomolny(int *Val, int N, int k) {
    static int l = -1;
    int i;
    // 開始時にレベルを0に設定する
    l = l + 1;
    Val[k] = l;
    if (l == N)
        display(Val, N);
    else
        for (i = 0; i < N; i++)
            // 値が0（未使用）の位置にのみ値を割り当てる
            if (Val[i] == 0)
                AlexanderBogomolny(Val, N, i);
    // そのレベル以降のすべての順列を生成し終えたら、レベルを1つ戻す
    l = l - 1;
    Val[k] = 0;
}

int main() {
    int i, N, cnt = 1;
    cout << "並べ替える先頭N個の自然数の個数を入力してください: ";
    cin >> N;
    int Val[N];
    for (i = 0; i < N; i++) {
        Val[i] = 0;
        cnt *= (i + 1);  // 順列の総数 N! を計算
    }
    cout << "\n可能な順列の総数: " << cnt;
    cout << "\n\nAlexander Bogomolnyのアルゴリズムによる順列生成\n";
    AlexanderBogomolny(Val, N, 0);
    return 0;
}

実行結果

N = 5 を入力した場合の出力例です。5! = 120 通りの順列がすべて表示されます（以下は冒頭部分の抜粋）。

並べ替える先頭N個の自然数の個数を入力してください: 5

可能な順列の総数: 120

Alexander Bogomolnyのアルゴリズムによる順列生成
   1   2   3   4   5
   1   2   3   5   4
   1   2   4   3   5
   1   2   5   3   4
   1   2   4   5   3
   1   2   5   4   3
   1   3   2   4   5
   ...
   5   4   3   2   1

実装のポイント

• static変数 l: 再帰呼び出し全体で共有され、現在配置中の要素の番号（レベル）を追跡します。
• バックトラック処理: 各再帰の終了時に l をデクリメントし、Val[k] を0に戻すことで、次の候補を試せる状態に配列を復元します。
• 計算量への注意: 順列の総数はN!で急増するため、Nが大きいと出力が膨大になります。動作確認はN ≤ 10程度までが現実的です。