C++ प्रोग्राम: Alexander Bogomolny का अनऑर्डर्ड परम्यूटेशन एल्गोरिदम

यह C++ प्रोग्राम Alexander Bogomolny के अनऑर्डर्ड परम्यूटेशन एल्गोरिदम को लागू करता है जो 1 से N तक के प्राकृतिक संख्याओं के सभी परम्यूटेशन (क्रमचय) जनरेट करता है।

एल्गोरिदम

शुरुआत
  1. फंक्शन AlexanderBogomolny():
     आर्गुमेंट्स: Val[] = ऐरे, N = तत्वों की संख्या, K = लेवल
     बॉडी:
     - l = -1 इनिशियलाइज़ करें
     - l = l + 1
     - Val[k] = l
     - यदि l == N तो display(Val, N) कॉल करें
     - अन्यथा i = 0 से N-1 तक:
         यदि Val[i] == 0 तो AlexanderBogomolny(Val, N, i) कॉल करें
         l = l - 1
         Val[k] = 0
समाप्ति

उदाहरण कोड

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

void display(const int *arr, const int size) {
    if (arr != 0) {
        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 = level + 1;
    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 = level - 1;
    Val[k] = 0;
}

int main() {
    int N;
    cout << "Enter N to permute first N natural numbers: ";
    cin >> N;
    
    int Val[N];
    long long factorial = 1;
    for (int i = 0; i < N; i++) {
        Val[i] = 0;
        factorial *= (i + 1);
    }
    
    cout << "\nNumber of permutations possible: " << factorial;
    cout << "\n\nPermutations using Alexander Bogomolny's Algorithm:\n";
    AlexanderBogomolny(Val, N, 0);
    return 0;
}

आउटपुट (N=3 के लिए संक्षिप्त)

Enter N to permute first N natural numbers: 3
Number of permutations possible: 6

Permutations using Alexander Bogomolny's Algorithm:
   1   2   3
   1   3   2
   2   1   3
   2   3   1
   3   1   2
   3   2   1

व्याख्या: यह एल्गोरिदम बैकट्रैकिंग का उपयोग करता है जहां level स्टेटिक वेरिएबल वर्तमान गहराई ट्रैक करता है। प्रत्येक रिकर्सिव कॉल एक पोजीशन भरती है। जब लेवल N तक पहुंचता है, तो एक पूर्ण परम्यूटेशन प्रिंट होता है। समय जटिलता O(N × N!) है।

नोट: N=5 के लिए 120 परम्यूटेशन होते हैं जो आउटपुट में बहुत बड़े होते हैं।