C++で実装するAlexander Bogomolnyの順列生成アルゴリズム

本記事では、数値Nが与えられたとき、Alexander Bogomolnyの順序なし順列アルゴリズム（UnOrdered Permutation Algorithm）を用いて、1からNまでのすべての順列を求める方法を解説します。

順列とは

順列（permutation）とは、集合内の要素を一意に並べ替える方法の総数、またはその並べ方そのものを指します。

例：{4, 9, 2}の順列は、{4, 9, 2}、{4, 2, 9}、{9, 4, 2}、{9, 2, 4}、{2, 4, 9}、{2, 9, 4}の6通りとなります。

順列はコンピュータネットワークにおけるスイッチングネットワークの設計や、並列処理の分野で活用されているほか、さまざまな暗号化アルゴリズムにも応用されています。

Alexander Bogomolnyの順序なし順列アルゴリズムとは

このアルゴリズムは、最初のN個の自然数（1からNまで）について、考えられるすべての順列を計算します。数値Nが与えられると、1からNまでの数字を使った順列をすべて出力します。

入力例と出力例

入力：

N = 3

出力：

1,2,3 ; 1,3,2 ; 2,1,3 ; 2,3,1 ; 3,1,2 ; 3,2,1

アルゴリズムの手順

1. 配列・数値N・整数kを引数とする関数を定義する
2. レベル（level）を初期化し、レベルが進むごとに残りの値を入れ替えていく
3. 再帰の終了条件に達した時点で、その時点のすべての値を出力する

C++による実装例

以下は、このアルゴリズムを実装したプログラムです。

#include <iostream>
using namespace std;
int level = -1;
void AlexanderBogomolyn(int permutations[], int N, int k) {
    level = level + 1;
    permutations[k] = level;
    if (level == N) {
        for (int i = 0; i < N; i++)
            cout<<permutations[i]<<"	";
        cout<<endl;
    }
    else{
        for (int i = 0; i < N; i++)
            if (permutations[i] == 0)
                AlexanderBogomolyn(permutations, N, i);
    }
    level = level - 1;
    permutations[k] = 0;
}
int main(){
    int N = 4;
    int permutations[N] = { 0 };
    cout<<"All permutations are :
";
    AlexanderBogomolyn(permutations, N, 0);
    return 0;
}

実行結果

All permutations are :
1 2 3 4
1 2 4 3
1 3 2 4
1 4 2 3
1 3 4 2
1 4 3 2
2 1 3 4
2 1 4 3
3 1 2 4
4 1 2 3
3 1 4 2
4 1 3 2
2 3 1 4
2 4 1 3
3 2 1 4
4 2 1 3
3 4 1 2
4 3 1 2
2 3 4 1
2 4 3 1
3 2 4 1
4 2 3 1
3 4 2 1
4 3 2 1

アルゴリズムのポイント

この実装では、グローバル変数levelが現在の再帰の深さを追跡し、配列permutationsが各位置に割り当てられた数値を管理します。まだ使用されていない位置（値が0の場所）に対して再帰的に関数を呼び出すことで、重複のない順列を効率的に生成できます。レベルがNに達すると1つの完全な順列が出力され、バックトラッキングによって次の組み合わせへと進みます。このように再帰とバックトラッキングを組み合わせることで、N!通りの順列をすべて網羅的に求めることが可能です。