Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम: दिए गए सेट के सभी सबसेट को लेक्सिकोग्राफिक ऑर्डर में जनरेट करें


यह दिए गए सेट के सभी सबसेट को लेक्सिकोग्राफिक ऑर्डर में जनरेट करने का C++ प्रोग्राम है। यह एल्गोरिदम दिए गए ऐरे के सेट से प्रत्येक लंबाई के सभी संभावित संयोजन को बढ़ते क्रम में प्रिंट करता है। इस एल्गोरिदम की समय जटिलता O(n*(2^n)) है।

एल्गोरिदम

Begin    प्रत्येक लंबाई 'i' के लिए GenAllSubset() फंक्शन कॉल किया जाता है:    1) GenAllSubset() में, यदि currLen, reqLen से अधिक है तो वापस लौटें।    2) अन्यथा, यदि currLen, reqLen के बराबर है तो एक नया अनुक्रम उत्पन्न होगा, इसे प्रिंट करें।    3) यदि 'true' के रूप में स्टार्ट के साथ आगे बढ़ें और 'currLen' और 's' के इन्क्रीमेंटेड मान के साथ GenAllSubset() को रिकर्सिवली कॉल करें।    अन्यथा       'false' के रूप में स्टार्ट के साथ आगे बढ़ें और 's' के इन्क्रीमेंटेड मान के साथ GenAllSubset() को रिकर्सिवली कॉल करें। 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";       cout<<"{ ";       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;    bool ch[n];    cout<<"Enter the number of element array have: ";    cin>>n;    int arr[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 }

  1. - C++ प्रोग्राम दी गई संख्या के अंकों का योग करने के लिए

    C++ भाषा में अंकों का योग गणना करने का एक उदाहरण निम्नलिखिक है, उदाहरण #include<iostream> using namespace std; int main() {    int x, s = 0;    cout << "संख्या दर्ज करें: ";    cin >> x;    while (x != 0) {       s =

  1. - Python प्रोग्राम से दिए गए आकार के सेट के सभी सबसेट प्राप्त करना

    इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे। समस्या कथन - हमें एक सेट दिया गया है, हमें आकार n के सभी सबसेट सूचीबद्ध करने की आवश्यकता है। समस्या को हल करने के लिए हमारे पास तीन दृष्टिकोण हैं। itertools.combinations() मेथड का उपयोग करना उदाहरण # itertools मॉड्यूल import ite

  1. - Python प्रोग्राम से दिए गए आकार के सेट के सभी सबसेट प्राप्त करना (दोहराया गया)

    इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे। समस्या कथन - हमें दो पूर्णांक दिए गए हैं, हमें दो संख्याओं के सामान्य भाजक प्रदर्शित करने की आवश्यकता है। यहां हम इनपुट के रूप में ली गई दो संख्याओं के न्यूनतम की गणना करते हैं। 1 से न्यूनतम गणना तक प्रत्येक मान को विभाजित करके भ