Thuật toán hoán vị không thứ tự của Alexander Bogomolny trong C++

Cho số N, tìm tất cả hoán vị của N số tự nhiên đầu tiên bằng thuật toán Alexander Bogomolny.

Hoán vị (Permutation) là các cách sắp xếp duy nhất các phần tử trong tập hợp.

Ví dụ: Hoán vị của {4,9,2}: {4,9,2}, {4,2,9}, {9,4,2}, {9,2,4}, {2,4,9}, {2,9,4}.

Ứng dụng: mạng chuyển mạch, xử lý song song, mật mã học.

Thuật toán Bogomolny

Đệ quy với mảng perm[], cấp độ (level) tăng dần. Khi level == N, in hoán vị.

void Bogomolny(int perm[], int N, int k) {
    level++;
    perm[k] = level;
    if (level == N) {
        for (int i = 0; i < N; i++) cout << perm[i] << "\t";
        cout << endl;
    } else {
        for (int i = 0; i < N; i++)
            if (perm[i] == 0) Bogomolny(perm, N, i);
    }
    level--;
    perm[k] = 0;
}

Ví dụ mã nguồn

#include <iostream>
using namespace std;

int level = -1;

void Bogomolny(int perm[], int N, int k) {
    level++;
    perm[k] = level;
    if (level == N) {
        for (int i = 0; i < N; i++) cout << perm[i] << "\t";
        cout << endl;
    } else {
        for (int i = 0; i < N; i++)
            if (perm[i] == 0) Bogomolny(perm, N, i);
    }
    level--;
    perm[k] = 0;
}

int main() {
    int N = 4;
    int perm[4] = {0};
    cout << "Tất cả hoán vị:\n";
    Bogomolny(perm, N, 0);
    return 0;
}

Kết quả (N=4)

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
... (tổng 24 hoán vị)