Chương trình C++ hoán vị Alexander Bogomolny (1 đến N)

Triển khai thuật toán hoán vị không theo thứ tự của Alexander Bogomolny để sinh tất cả hoán vị của N số tự nhiên đầu tiên.

Thuật toán

Hàm AlexanderBogomolny(Val[], N, k):
  static level = -1.
  level++; Val[k] = level.
  Nếu level == N: in Val[].
  Ngược lại:
    Với i từ 0 đến N-1:
      Nếu Val[i] == 0: AlexanderBogomolny(Val, N, i).
  level--; Val[k] = 0.

Ví dụ mã nguồn

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

void display(const int* arr, int size) {
    for (int i = 0; i < size; i++) cout << setw(4) << arr[i];
    cout << "\n";
}

void AlexanderBogomolny(int* Val, int N, int k) {
    static int level = -1;
    level++;
    Val[k] = level;
    if (level == N) display(Val, N);
    else {
        for (int i = 0; i < N; i++)
            if (Val[i] == 0) AlexanderBogomolny(Val, N, i);
    }
    level--;
    Val[k] = 0;
}

int main() {
    int N;
    cout << "Nhap N: "; cin >> N;
    int Val[N] = {0};
    long long cnt = 1;
    for (int i = 1; i <= N; i++) cnt *= i;
    cout << "So hoan vi: " << cnt << "\n\n";
    AlexanderBogomolny(Val, N, 0);
    return 0;
}

Đầu ra (N=3)

So hoan vi: 6
   1   2   3
   1   3   2
   2   1   3
   2   3   1
   3   1   2
   3   2   1