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

«
»
This is a C Program to generate all subsets of given set of numbers using gray code order. The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one bit (binary digit). The reflected binary code was originally designed to prevent spurious output from electromechanical switches.

Here is source code of the C Program to Generate All Subsets of a Given Set in the Gray Code Order. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<stdio.h>
  2. #include<math.h>
  3. int i, j;
  4. int sequence[] = { 2, 3, 5, 6, 7 };
  5.  
  6. void grayCode(int N) {
  7.     int grayCode[(int) pow(2, N)];
  8.     int binary[(int) pow(2, N)];
  9.  
  10.     for (i = 0; i < pow(2, N); i++)
  11.         grayCode[i] = (i >> 1) ^ i;
  12.  
  13.     for (i = 0; i < pow(2, N); i++) {
  14.         int b = 1;
  15.         binary[i] = 0;
  16.         while (grayCode[i] > 0) {
  17.             binary[i] += (grayCode[i] % 2) * b;
  18.             grayCode[i] /= 2;
  19.             b = b * 10;
  20.         }
  21.     }
  22.     printf("\nThe permutations are: ");
  23.     for (i = 0; i < pow(2, N); i++) {
  24.         printf("{ ");
  25.         for (j = 0; j < N; j++) {
  26.             if (binary[i] % 10 == 1)
  27.                 printf("%d ", sequence[j]);
  28.             binary[i] /= 10;
  29.         }
  30.         printf("}\n");
  31.     }
  32. }
  33.  
  34. int main(int argc, char **argv) {
  35.     printf("The elements in the set : ");
  36.     for (i = 0; i < 5; i++)
  37.         printf("%d ", sequence[i]);
  38.  
  39.     int mask[(int) pow(2, 5)];
  40.     grayCode(5);
  41.     return 0;
  42. }

Output:

advertisement
$ gcc GrayCode.c
$ ./a.out
 
The elements in the set : 2 3 5 6 7 
The permutations are: { }
{ 2 }
{ 2 3 }
{ 3 }
{ 3 5 }
{ 2 3 5 }
{ 2 5 }
{ 5 }
{ 5 6 }
{ 2 5 6 }
{ 2 3 5 6 }
{ 3 5 6 }
{ 3 6 }
{ 2 3 6 }
{ 2 6 }
{ 6 }
{ 6 7 }
{ 2 6 7 }
{ 2 3 6 7 }
{ 3 6 7 }
{ 3 5 6 7 }
{ 2 3 5 6 7 }
{ 2 5 6 7 }
{ 5 6 7 }
{ 5 7 }
{ 2 5 7 }
{ 2 3 5 7 }
{ 3 5 7 }
{ 3 7 }
{ 2 3 7 }
{ 2 7 }
{ 7 }

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and 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.