Question

Implement the binary reflected Gray code algorithm for generating subsets in Java

Answer 1

// Generating n-bit Gray codes
import java.util.*;
class GfG {

// It generates all n bit Gray codes and outputs the generated codes
static void generateGraycodes(int n)
{
   if (n <= 0)
       return;

   // 'sets' will store all generated codes
   ArrayList<String> sets= new ArrayList<String> ();

   // start with 1-bit pattern
    sets.add("0");
    sets.add("1");

   // Every iteration of this loop generates 2*i codes from previously
   // generated i codes.
   int i, j;
   for (i = 2; i < (1<<n); i = i<<1)
   {
       // Enter the prviously generated codes again in sets[] in reverse
       // order. Nor sets[] has double number of codes.
       for (j = i-1 ; j >= 0 ; j--)
            sets.add(sets.get(j));

       // append 0 to the first half
       for (j = 0 ; j < i ; j++)
            sets.set(j, "0" + sets.get(j));

       // append 1 to the second half
       for (j = i ; j < 2*i ; j++)
            sets.set(j, "1" + sets.get(j));
   }

   // print contents of sets[]
   for (i = 0 ; i < sets.size() ; i++ )
       System.out.println(sets.get(i));
}

//Main Function
public static void main(String[] args)
{
   generateGraycodes(3);
}
}