Code:
#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<
}
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 "<
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;
}
Output:
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 }
More C++ Programs:
