C++でのAlexanderBogomolnyの順序付けされていない順列アルゴリズム

ここでは、番号Nが与えられています。私たちのタスクは、AlexanderBogomolnyのUnorderedPermutationAlgorithmを使用してNの無秩序な順列を見つけることです。

最初に順列について説明しましょう

順列 セット内のアイテムを一意に並べ替えることができる方法の数は、順列と呼ばれます。

例 − {4,9,2}の順列は、{4,9,2}、{4,2,9}、{9,4,2}、{9,2,4}、{2,4,9 }および{2,9,4}。

順列は、コンピュータネットワーク、並列処理でスイッチングネットワークを定義する際に使用され、さまざまな暗号化アルゴリズムでも使用されています。

AlexanderBogomolnyの順序付けられていない順列アルゴリズム

このアルゴリズムは、最初の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. Build a function with an array, number N, and an integer k as
parameters
2. Initialize the level, as level increases permute the rest of the values
3. When the recursion condition is reached all its values are printed.

例

アルゴリズムの実装を示すプログラム-

#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]<<"\t";
      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 :\n";
   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