C++ Program to Generate All Pairs of Subsets whose Union Make the Set

This is a C++ program to generate all pairs of subsets whose union make the set.

Problem Description

1. This algorithm generates all pairs of subsets whose union make the set.
2. The time complexity of this algorithm is O(n*2^n).

Problem Solution

1. This algorithm takes the input of ‘n’ data element and prints unique subset pairs whose union gives the set.
2. For that, it generates 0 to 2^(n-1) bit random sequence of 0 or 1 using binary counting.
3. Print the elements in the pairs which have 1 or 0 at the corresponding indexes.
4. Exit.

Program/Source Code

C++ Program to generate a random subset by coin flipping.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#include<iostream>
#include<math.h>
#include<iomanip>
 
using namespace std;
 
// A function to print array element according to the code in the argument list.
void print(char code[], int arr[], int n)
{
	int i;
	cout<<"\t{ ";
	for(i = 0; i < n; i++)
	{
		// Print if the corresponding value is 1.
		if(code[i] == '1')
			cout<<arr[i]<<" ";
	}
	cout<<"}";
	cout<<"        { ";
	for(i = 0; i < n; i++)
	{
		// Print if the corresponding value is 0.
		// It will print the remaining elements which on union forms the superset.
		if(code[i] == '0')
			cout<<arr[i]<<" ";
	}
	cout<<"}\n";
}
 
void GenUnionSet(int arr[], 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++)
	{
		print(binary, arr, n);
		l=n-1;
 
		// Incrementing the binary value with each iteration.
		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 element array have: ";
	cin>>n;
 
	int arr[n];
	cout<<"\n";
 
	// Take the input of the array.
	for(i = 0; i < n; i++)
	{
		cout<<"Enter "<<i+1<<" element: ";
		cin>>arr[i];
	}
 
	// Print the subset using binary counting method.
	cout<<"\nThe possible subset pairs which on union generates the superset, are: \n";
	GenUnionSet(arr, n);
 
	return 0;
}

Program Explanation

1. Take the input of an array of ‘n’ data element.
2. Call GenUnionSet() with the array ‘arr’ and length ‘n’ in the argument list.
3. For all 2^(n-1) pairs generate binary code from 0 to 2^(n-1)-1.
4. For each code print the array element which has 0 or 1 in corresponding indexes in code string.
5. Print them in a different set, which on the union of both sets gives the super set.
6. Exit.

Runtime Test Cases

Case 1:
Enter the number of element array have: 5
 
Enter 1 element: 1
Enter 2 element: 2
Enter 3 element: 3
Enter 4 element: 4
Enter 5 element: 5
 
The possible subset pairs which on union generates the superset, are:
        { }        { 1 2 3 4 5 }
        { 5 }        { 1 2 3 4 }
        { 4 }        { 1 2 3 5 }
        { 4 5 }        { 1 2 3 }
        { 3 }        { 1 2 4 5 }
        { 3 5 }        { 1 2 4 }
        { 3 4 }        { 1 2 5 }
        { 3 4 5 }        { 1 2 }
        { 2 }        { 1 3 4 5 }
        { 2 5 }        { 1 3 4 }
        { 2 4 }        { 1 3 5 }
        { 2 4 5 }        { 1 3 }
        { 2 3 }        { 1 4 5 }
        { 2 3 5 }        { 1 4 }
        { 2 3 4 }        { 1 5 }
        { 2 3 4 5 }        { 1 }
Case 2:
Enter the number of element array have: 4
 
Enter 1 element: 1
Enter 2 element: 2
Enter 3 element: 3
Enter 4 element: 4
 
The possible subset pairs which on union generates the superset, are:
        { }        { 1 2 3 4 }
        { 4 }        { 1 2 3 }
        { 3 }        { 1 2 4 }
        { 3 4 }        { 1 2 }
        { 2 }        { 1 3 4 }
        { 2 4 }        { 1 3 }
        { 2 3 }        { 1 4 }
        { 2 3 4 }        { 1 }

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Perform Edge Coloring to the Line Graph of an Input Graph

» Next - C++ Program to Generate a Random Subset by Coin Flipping

Related Posts:

Recommended Articles: