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.

advertisement
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.

advertisement
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.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn