C++ Programming Code Examples

C++ > Beginners Lab Assignments Code Examples

Program to Generate All Subsets of a Given Set in the Gray Code Order



Program to Generate All Subsets of a Given Set in the Gray Code Order

- This algorithm print all the possible combination of each length from the given array in gray code 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 generates the gray code and prints the corresponding array element of the array.
- Exit.

#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;
}