Java Program to Generate All Possible Subsets using Gray Code Order

This is a java program to generate and print all the subsets using the 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 gray code equivalent of a binary number is (number >> 1) ^ number, i.e. right-shift the number by one and EX-ORing with the original number.

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

  1. //This is a java program to generate all subsets of given set of numbers using gray code order
  2. import java.util.Random;
  3. import java.util.Scanner;
  4.  
  5. public class Gray_Code_Permutation 
  6. {
  7.     public static int[] grayCode(int N) 
  8.     {
  9.         int[] grayCode = new int[(int) Math.pow(2, N)];
  10.         int[] binary = new int[(int) Math.pow(2, N)];
  11.  
  12.         for (int i = 0; i < Math.pow(2, N); i++)
  13.             grayCode[i] = (i >> 1) ^ i;
  14.  
  15.         for (int i = 0; i < Math.pow(2, N); i++) 
  16.         {
  17.             int b = 1;
  18.             binary[i] = 0;
  19.             while (grayCode[i] > 0) 
  20.             {
  21.                 binary[i] += (grayCode[i] % 2) * b;
  22.                 grayCode[i] /= 2;
  23.                 b = b * 10;
  24.             }
  25.         }
  26.         return binary;
  27.     }
  28.  
  29.     public static void main(String args[]) 
  30.     {
  31.         Random random = new Random();
  32.         Scanner sc = new Scanner(System.in);
  33.         System.out.println("Enter the number of elements in the set: ");
  34.         int N = sc.nextInt();
  35.         int[] sequence = new int[N];
  36.         for (int i = 0; i < N; i++)
  37.             sequence[i] = Math.abs(random.nextInt(100));
  38.  
  39.         System.out.println("The elements in the set : ");
  40.         for (int i = 0; i < N; i++)
  41.             System.out.print(sequence[i] + " ");
  42.  
  43.         int[] mask = new int[(int) Math.pow(2, N)];
  44.         mask = grayCode(N);
  45.  
  46.         System.out.println("\nThe permutations are: ");
  47.         for (int i = 0; i < Math.pow(2, N); i++) 
  48.         {
  49.             System.out.print("{ ");
  50.             for (int j = 0; j < N; j++) 
  51.             {
  52.                 if (mask[i] % 10 == 1)
  53.                     System.out.print(sequence[j] + " ");
  54.                 mask[i] /= 10;
  55.             }
  56.             System.out.println("}");
  57.         }
  58.         sc.close();
  59.     }
  60. }

Output:

$ javac Gray_Code_Permutation.java
$ java Gray_Code_Permutation
 
Enter the number of elements in the set: 
4
The elements in the set : 
36 75 15 59 
The permutations are: 
{ }
{ 36 }
{ 36 75 }
{ 75 }
{ 75 15 }
{ 36 75 15 }
{ 36 15 }
{ 15 }
{ 15 59 }
{ 36 15 59 }
{ 36 75 15 59 }
{ 75 15 59 }
{ 75 59 }
{ 36 75 59 }
{ 36 59 }
{ 59 }
 
Enter the number of elements in the set: 
3
The elements in the set : 
73 36 36 
The permutations are: 
{ }
{ 73 }
{ 73 36 }
{ 36 }
{ 36 36 }
{ 73 36 36 }
{ 73 36 }
{ 36 }

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.