C++ प्रोग्राम: सभी सबसेट जोड़ियां उत्पन्न करना जिनका यूनियन सुपरसेट बनाता है

यह C++ प्रोग्राम दिए गए सेट के सभी संभावित सबसेट जोड़े उत्पन्न करता है जिनका यूनियन (union) मूल सेट (सुपरसेट) बनाता है। प्रत्येक जोड़े में दो पूरक (complementary) सबसेट होते हैं।

एल्गोरिदम

शुरुआत
  1. फंक्शन UnionSet():
     आर्गुमेंट्स: a[] = ऐरे, n = तत्वों की संख्या
     बॉडी:
     1) 0 से 2^(n-1)-1 तक बाइनरी कोड जनरेट करें सभी 2^(n-1) जोड़ियों के लिए।
     2) प्रत्येक कोड के लिए, ऐरे के उन तत्वों को प्रिंट करें जिनके संबंधित इंडेक्स में 0 या 1 है।
     3) उन्हें दो अलग-अलग सेट में प्रिंट करें जिनका यूनियन सुपरसेट देता है।
समाप्ति

उदाहरण कोड

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

void display(char code[], int a[], int n) {
    int i;
    cout << "\t{ ";
    for (i = 0; i < n; i++) {
        if (code[i] == '1')
            cout << a[i] << " ";
    }
    cout << "} { ";
    for (i = 0; i < n; i++) {
        if (code[i] == '0')
            cout << a[i] << " ";
    }
    cout << "}\n";
}

void UnionSet(int a[], int n) {
    int i, r, l;
    char binary[n];
    r = pow(2, n-1);
    
    for (i = 0; i < n; i++) binary[i] = '0';
    
    for (i = 0; i < r; i++) {
        display(binary, a, n);
        l = n - 1;
        h:
        if (binary[l] == '0')
            binary[l] = '1';
        else {
            binary[l] = '0';
            l--;
            goto h;
        }
    }
}

int main() {
    int i, n;
    cout << "\nEnter the number of elements: ";
    cin >> n;
    int a[n];
    cout << "\n";
    for (i = 0; i < n; i++) {
        cout << "Enter " << i+1 << " element: ";
        cin >> a[i];
    }
    cout << "\nThe possible subset pairs which on union generates the superset, are: \n";
    UnionSet(a, n);
    return 0;
}

आउटपुट

Enter the number of elements: 4
Enter 1 element: 4
Enter 2 element: 3
Enter 3 element: 2
Enter 4 element: 1

The possible subset pairs which on union generates the superset, are:
{ } { 4 3 2 1 }
{ 1 } { 4 3 2 }
{ 2 } { 4 3 1 }
{ 2 1 } { 4 3 }
{ 3 } { 4 2 1 }
{ 3 1 } { 4 2 }
{ 3 2 } { 4 1 }
{ 3 2 1 } { 4 }

व्याख्या: n तत्वों के सेट के लिए, 2^(n-1) ऐसे अनोखे जोड़े होते हैं। प्रोग्राम बाइनरी काउंटिंग का उपयोग करता है जहां प्रत्येक बिट एक तत्व की उपस्थिति (1) या अनुपस्थिति (0) को दर्शाता है। पहला सेट 1-बिट्स दिखाता है, दूसरा 0-बिट्स दिखाता है।