Alexander Bogomolny의 C++에서 정렬되지 않은 순열 알고리즘

여기에 N이 주어졌습니다. 우리의 임무는 Alexander Bogomolny의 UnOrdered Permutation Algorithm을 사용하여 N의 순서가 없는 순열을 찾는 것입니다.

먼저 순열에 대해 논의하겠습니다.

순열 세트의 항목이 고유하게 정렬될 수 있는 방법의 수를 순열이라고 합니다.

예 − {4,9,2}의 순열은 {4,9,2}, {4,2,9}, {9,4,2}, {9,2,4}, {2,4,9입니다. } 및 {2,9,4}.

순열은 컴퓨터 네트워킹, 병렬 처리 및 다양한 암호화 알고리즘에서 스위칭 네트워크를 정의하는 데 사용됩니다.

Alexander Bogomolny의 정렬되지 않은 순열 알고리즘

이 알고리즘은 처음 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