C++ Programming Code Examples

C++ > Computer Graphics Code Examples

Program to Generate All Subsets of a Given Set in the Lexico Graphic Order



Program to Generate All Subsets of a Given Set in the Lexico Graphic Order

- This algorithm print all the possible combination of each length from the given array in increasing order.
- The time complexity of this algorithm is O(n*(2^n)).

- This algorithm takes the input of 'n' data element and prints all possible combination.
- For that, it sorts the input array and maintains a boolean array 'n'.
- If the corresponding boolean value is true, then it prints that element.
- Exit.

#include<iostream>
 
using namespace std;
 
// A function to sort the data set.
void Sort(int a[], int n)
{
	int i, j, temp;
 
	for(i = 0; i < n; i++)
	{
		for(j = i+1; j < n; j++)
		{
			if(a[i] > a[j])
			{
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
	}
}
 
// A function to print all combination of a given length from the given array.
void GenSubset(int a[], int reqLen, int start, int currLen, bool check[], int len) 
{
	// Return if the currLen is more than the required length.
	if(currLen > reqLen)
	return;
	// If currLen is equal to required length then print the sequence.
	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 start equals to len then return since no further element left.
	if (start == len) 
	{
		return;
	}
	// For every index we have two options.
	// First is, we select it, means put true in check[] and increment currLen and start.
	check[start] = true;
	GenSubset(a, reqLen, start + 1, currLen + 1, check, len);
	// Second is, we don't select it, means put false in check[] and only start incremented.
	check[start] = false;
	GenSubset(a, reqLen, start + 1, currLen, check, len);
}
}
 
int main()
{
	int i, n;
	bool check[n];
	cout<<"Enter 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];
		check[i] = false;
	}
 
	// Sort the array.
	Sort(arr, n);
 
	cout<<"\nThe subset in the lexicographic order: \n";
	cout<<"\t{ }\n";
	for(i = 1; i <= n; i++)
	{
		GenSubset(arr, i, 0, 0, check, n);
	}
	return 0;
}