C++ Program to Generate All Possible Subsets using Gray Code Order

«
»

This is a C++ program to generate all subsets of a given set in the gray code order.

Problem Description

1. This algorithm print all the possible combination of each length from the given array in gray code order.
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 all possible combination.
2. For that, it generates the gray code and prints the corresponding array element of the array.
3. Exit.

Program/Source Code

C++ Program to generate all subsets of a given set in the gray code order.
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>
 
using namespace std;
 
// A function to print array element according to the code in the argument list.
void print(int code[], int arr[], int n)
{
	int i;
	cout<<"\t{ ";
	for(i = 0; i < n; i++)
	{
		// Print if the corresponding value is true.
		if(code[i] == 1)
			cout<<arr[i]<<" ";
	}
	cout<<"}\n";
}
 
// A function generating gray codes.
void GenGrayCode(int arr[], int n) 
{ 
	int r, i, k, j, l, code[n], a[n];
	r = pow(2,n);
 
	// External loop to generate 2^n subsets.
	for(i = 0; i < r; i++)
	{
		k=i;
 
		// Loop to store the i value in binary in the a[] array.
		for(j = n-1; j >= 0; j--, k /= 2) 
			a[j] = k%2;
 
		k = 0 ;
		l = 0;
 
		// From the binary value generate the corresponding gray code.
		for(j = 0;  j < n; j++)
		{
			// If the first value is 1 then assign it into the gray code array
			if(k == 0)
			{
				if(a[j] == 1) 
					k++; 
				code[l] = a[j];
				l++; 
			}
			// If the current bit in the binary code is equal to the previous value then assign the corresponding gray code value to 0.
			else if(a[j] == a[j-1])
			{
				code[l] = 0;
				l++;
		 	}
		 	// Otherwise assign the corresponding gray code value to 1.
			else
			{
				code[l] = 1;
				l++;
			}
		}
		// As the next code generated, call print().
		print(code , arr, n);
	}
}
 
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 in the gray code order.
	cout<<"\nThe subset in the gray code order: \n";
	GenGrayCode(arr, n);
 
	return 0;
}
Program Explanation

1. Take the input of an array of ‘n’ data element.
2. Call GenGreyCode() function with data array and n in the argument list.
3. Inside GenGreyCode(), Calculate the total subset as ‘r=pow(2,n)’.
4. Generate the gray code for each subset.
5. Call print() to print only those array element which has 1 as their corresponding gray code value.
6. Exit.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
Runtime Test Cases
Case 1:
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 subset in the gray code order:
        { }
        { 4 }
        { 3 4 }
        { 3 }
        { 2 3 }
        { 2 3 4 }
        { 2 4 }
        { 2 }
        { 1 2 }
        { 1 2 4 }
        { 1 2 3 4 }
        { 1 2 3 }
        { 1 3 }
        { 1 3 4 }
        { 1 4 }
        { 1 }
 
Case 2:
Enter the number of element array have: 5
 
Enter 1 element: 5
Enter 2 element: 4
Enter 3 element: 3
Enter 4 element: 2
Enter 5 element: 1
 
The subset in the gray code order:
        { }
        { 1 }
        { 2 1 }
        { 2 }
        { 3 2 }
        { 3 2 1 }
        { 3 1 }
        { 3 }
        { 4 3 }
        { 4 3 1 }
        { 4 3 2 1 }
        { 4 3 2 }
        { 4 2 }
        { 4 2 1 }
        { 4 1 }
        { 4 }
        { 5 4 }
        { 5 4 1 }
        { 5 4 2 1 }
        { 5 4 2 }
        { 5 4 3 2 }
        { 5 4 3 2 1 }
        { 5 4 3 1 }
        { 5 4 3 }
        { 5 3 }
        { 5 3 1 }
        { 5 3 2 1 }
        { 5 3 2 }
        { 5 2 }
        { 5 2 1 }
        { 5 1 }
        { 5 }

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.