อัลกอริทึม Alexander Bogomolny สำหรับ Unordered Permutation ใน C++

กำหนดให้มีจำนวน N ภารกิจคือหา Unordered Permutation ของ N โดยใช้ Alexander Bogomolny's UnOrdered Permutation Algorithm

Permutation คืออะไร?

Permutation (การเรียงสับเปลี่ยน) คือจำนวนวิธีที่รายการในเซตสามารถเรียงลำดับได้อย่างไม่ซ้ำกัน

ตัวอย่าง: Permutation ของ {4,9,2} คือ {4,9,2}, {4,2,9}, {9,4,2}, {9,2,4}, {2,4,9}, {2,9,4}

Permutation ใช้ในเครือข่ายคอมพิวเตอร์ การประมวลผลแบบขนาน และอัลกอริทึมเข้ารหัส

อัลกอริทึม Alexander Bogomolny

อัลกอริทึมนี้คำนวณ Permutation ทั้งหมดของจำนวนธรรมชาติ 1 ถึง N

ตัวอย่าง

Input: N = 3
Output: 1,2,3 ; 1,3,2 ; 2,1,3 ; 2,3,1 ; 3,1,2 ; 3,2,1

อัลกอริทึม (ขั้นตอน)

1. สร้างฟังก์ชันรับอาร์เรย์, N, และ integer k
2. เพิ่มระดับ (level) ขึ้น 1, สลับค่าที่เหลือ
3. เมื่อเงื่อนไข recursion ถึง จะพิมพ์ค่าทั้งหมด

โค้ดตัวอย่าง

#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
... (รวม 24 แบบสำหรับ N=4)