Given a number N, write a function which generates all n-bit gray code sequences, a gray code sequence is a sequence such that successive patterns in it differ by one bit
Given a number N, write a function which generates all n-bit gray code sequences, a gray code sequence is a sequence such that successive patterns in it differ by one bit.
Construction an n bit gray code follows a robust algorithm. The binary-reflected Gray code list for n bits can be generated recursively from the list for n − 1 bits by reflecting the list (i.e. listing the entries in reverse order), prefixing the entries in the original list with a binary 0, prefixing the entries in the reflected list with a binary 1, and then concatenating the original list with the reversed list.
Let, the n-1 length gray code list has m elements, (m=2^(n-1))
Create list1 by adding prefix 0 to all the m elements
Create list2 by adding prefix 1 to all the m elements
New list for n-bit gray code= list1+reverse(list)
New list size 2m (2^n)
For any n bit gray code list, we start with gray code list of length 1 (elements are only '0' and '1'). Then iterate till finding n-bit gray code list.
The above can be explained with help of an example,
Let we need to find gray code sequence for n=3
//Base case
For n=1
List: 0, 1
For n=2
Add prefix '0' to create list1
List1= 00, 01
Add prefix '1' to create list2
List2= 10, 11
New list=list1 + reverse(list2)
=00, 01, 11, 10 //List for n=2
For n=3
Add prefix '0' to create list1
List1= 000, 001, 011, 010
Add prefix '1' to create list2
List2= 100, 101, 111, 110
New list=list1 + reverse(list2)
=000, 001, 011, 010, 110, 111, 101, 100 //List for n=3
Construction an n bit gray code follows a robust algorithm. The binary-reflected Gray code list for n bits can be generated recursively from the list for n − 1 bits by reflecting the list (i.e. listing the entries in reverse order), prefixing the entries in the original list with a binary 0, prefixing the entries in the reflected list with a binary 1, and then concatenating the original list with the reversed list.
Reference: Gray_code
Algorithm to generate n bit gray code list
For any n bit gray code list, we start with gray code list of length 1 (elements are only '0' and '1'). Then iterate till finding n-bit gray code list.
The above can be explained with help of an example,
C++ implementation
Output