C++ প্রোগ্রাম: দেওয়া সেটের সব সাবসেট লেক্সিকোগ্রাফিক অর্ডারে জেনারেট করা

এটি একটি C++ প্রোগ্রাম যা দেওয়া সেটের সকল সাবসেট লেক্সিকোগ্রাফিক অর্ডারে জেনারেট করে। এই অ্যালগরিদম অ্যারে থেকে প্রতিটি দৈর্ঘ্যের জন্য সব সম্ভাব্য কম্বিনেশন বর্ধমান ক্রমে প্রিন্ট করে। টাইম কমপ্লেক্সিটি O(n * 2^n)।

অ্যালগরিদম

Begin
    প্রতিটি দৈর্ঘ্য 'i'-র জন্য GenAllSubset() ফাংশন কল করুন:
    1) GenAllSubset()-এ, যদি currLen > reqLen হয়, তবে রিটার্ন করুন।
    2) অন্যথায়, যদি currLen == reqLen হয়, তবে নতুন সিকোয়েন্স জেনারেট হয়, প্রিন্ট করুন।
    3) যদি start 'true' হয়, তবে currLen এবং 's' ইনক্রিমেন্ট করে রিকারসিভ কল করুন।
       অন্যথায় start 'false' ধরে 's' ইনক্রিমেন্ট করে রিকারসিভ কল করুন।
End

উদাহরণ

#include <iostream>
using namespace std;

void Sorting(int a[], int n) {
    int i, j, t;
    for(i = 0; i < n; i++) {
        for(j = i+1; j < n; j++) {
            if(a[i] > a[j]) {
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
    }
}

void GenAllSubset(int a[], int reqLen, int s, int currLen, bool check[], int len) {
    if(currLen > reqLen) return;
    else if (currLen == reqLen) {
        cout << "\t{ ";
        for (int i = 0; i < len; i++) {
            if (check[i] == true)
                cout << a[i] << " ";
        }
        cout << "}\n";
        return;
    }
    if (s == len) return;
    check[s] = true;
    GenAllSubset(a, reqLen, s + 1, currLen + 1, check, len);
    check[s] = false;
    GenAllSubset(a, reqLen, s + 1, currLen, check, len);
}

int main() {
    int i, n;
    cout << "Enter the number of element array have: ";
    cin >> n;
    int arr[n];
    bool ch[n];
    cout << "\n";
    for (i = 0; i < n; i++) {
        cout << "Enter " << i+1 << " element: ";
        cin >> arr[i];
        ch[i] = false;
    }
    Sorting(arr, n);
    cout << "\nThe all subset of the given set in the lexicographic order: \n";
    cout << "\t{ }\n";
    for(i = 1; i <= n; i++)
        GenAllSubset(arr, i, 0, 0, ch, n);
    return 0;
}

আউটপুট

Enter the number of element array have: 6
Enter 1 element:3
Enter 2 element: 2
Enter 3 element: 1
Enter 4 element:7
Enter 5 element:6
Enter 6 element: 5
The all subset of the given set in the lexicographic order:
{ }
{ 1 }
{ 2 }
{ 3 }
{ 5 }
{ 6 }
{ 7 }
{ 1 2 }
{ 1 3 }
{ 1 5 }
{ 1 6 }
{ 1 7 }
{ 2 3 }
{ 2 5 }
{ 2 6 }
{ 2 7 }
{ 3 5 }
{ 3 6 }
{ 3 7 }
{ 5 6 }
{ 5 7 }
{ 6 7 }
{ 1 2 3 }
{ 1 2 5 }
{ 1 2 6 }
{ 1 2 7 }
{ 1 3 5 }
{ 1 3 6 }
{ 1 3 7 }
{ 1 5 6 }
{ 1 5 7 }
{ 1 6 7 }
{ 2 3 5 }
{ 2 3 6 }
{ 2 3 7 }
{ 2 5 6 }
{ 2 5 7 }
{ 2 6 7 }
{ 3 5 6 }
{ 3 5 7 }
{ 3 6 7 }
{ 5 6 7 }
{ 1 2 3 5 }
{ 1 2 3 6 }
{ 1 2 3 7 }
{ 1 2 5 6 }
{ 1 2 5 7 }
{ 1 2 6 7 }
{ 1 3 5 6 }
{ 1 3 5 7 }
{ 1 3 6 7 }
{ 1 5 6 7 }
{ 2 3 5 6 }
{ 2 3 5 7 }
{ 2 3 6 7 }
{ 2 5 6 7 }
{ 3 5 6 7 }
{ 1 2 3 5 6 }
{ 1 2 3 5 7 }
{ 1 2 3 6 7 }
{ 1 2 5 6 7 }
{ 1 3 5 6 7 }
{ 2 3 5 6 7 }
{ 1 2 3 5 6 7 }