http://www.geeksforgeeks.org/given-a-number-n-generate-bit-patterns-from-0-to-2n-1-so-that-successive-patterns-differ-by-one-bit/
The gray code is a binary numeral system where two successive values differ in only one bit.
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
n-bit Gray Codes can be generated from list of (n-1)-bit Gray codes using following steps.
1) Let the list of (n-1)-bit Gray codes be L1. Create another list L2 which is reverse of L1.
2) Modify the list L1 by prefixing a ’0′ in all codes of L1.
3) Modify the list L2 by prefixing a ’1′ in all codes of L2.
4) Concatenate L1 and L2. The concatenated list is required list of n-bit Gray codes.
1) Let the list of (n-1)-bit Gray codes be L1. Create another list L2 which is reverse of L1.
2) Modify the list L1 by prefixing a ’0′ in all codes of L1.
3) Modify the list L2 by prefixing a ’1′ in all codes of L2.
4) Concatenate L1 and L2. The concatenated list is required list of n-bit Gray codes.
For example, following are steps for generating the 3-bit Gray code list from the list of 2-bit Gray code list.
L1 = {00, 01, 11, 10} (List of 2-bit Gray Codes)
L2 = {10, 11, 01, 00} (Reverse of L1)
Prefix all entries of L1 with ’0′, L1 becomes {000, 001, 011, 010}
Prefix all entries of L2 with ’1′, L2 becomes {110, 111, 101, 100}
Concatenate L1 and L2, we get {000, 001, 011, 010, 110, 111, 101, 100}
http://huntfor.iteye.com/blog/2060142L1 = {00, 01, 11, 10} (List of 2-bit Gray Codes)
L2 = {10, 11, 01, 00} (Reverse of L1)
Prefix all entries of L1 with ’0′, L1 becomes {000, 001, 011, 010}
Prefix all entries of L2 with ’1′, L2 becomes {110, 111, 101, 100}
Concatenate L1 and L2, we get {000, 001, 011, 010, 110, 111, 101, 100}
格雷码， 提示中称：[0,2,3,1]也是一组合法的格雷码，把我彻底搞糊涂了，既然如此，为什么要返回[0,1,3,2]而不能返回[0,2,3,1]呢？后来手贱去百度了一下格雷码。尼玛....
看下格雷码的特征：
n == 1时，[0,1]
n == 2时，[00,01,11,10]
n == 3时，[000,001,011,010,110,111,101,100]
1位格雷码有两个码字
(n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0
(n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写，加前缀1
(n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0
(n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写，加前缀1
前后两部分的后n - 1位是对称的。
n的格雷码，就是n-1的格雷码，再加上它们的逆序前面多一个1。
当n=2时
00
01
11
10
当n=3时
000
001
011
010
110
111
101
100
可以发现，n的格雷码，就是n-1的格雷码，再加上它们的逆序前面多一个1。
public List<Integer> grayCode(int n) {
List<Integer> res = new ArrayList<Integer>();
// 加入初始值0
res.add(0);
for(int i = 0; i < n; i++){
// 每一轮的最高位
int highestBit = 1 << i;
int size = res.size();
// 逆序添加上一轮里出现的数，不过开头加上这一轮的最高位
for(int j = size - 1; j >= 0; j--){
int num = res.get(j);
num += highestBit;
res.add(num);
}
}
return res;
}
工业中的第i个格雷码是这么生成的：
i是指下标，从0开始，对于n的格雷码序列，一共有2^n个数
(i>>1)^ii是指下标，从0开始，对于n的格雷码序列，一共有2^n个数
public List<Integer> grayCode(int n) {
List<Integer> res = new ArrayList<Integer>();
for(int i = 0; i < 1 << n; i++) res.add((i >> 1)^i);
return res;
}
My idea is to generate the sequence iteratively. For example, when n=3, we can get the result based on n=2. 00,01,11,10 -> (000,001,011,010 ) (110,111,101,100). The middle two numbers only differ at their highest bit, while the rest numbers of part two are exactly symmetric of part one. It is easy to see its correctness. Code is simple:
public List<Integer> grayCode(int n) { List<Integer> rs=new ArrayList<Integer>(); rs.add(0); for(int i=0;i<n;i++){ int size=rs.size(); for(int k=size-1;k>=0;k--) rs.add(rs.get(k) | 1<<i); } return rs; }
We can see that the last two digits of 4 codes at the bottom is just the descending sequence of the first 4 codes. The first 4 codes are 0, 1, 3, 2. So, we can easily get the last 4 codes: 2 + 4, 3 + 4, 1 + 4, 0 + 4, which is 6, 7, 5, 4. We can keep doing this until we reach n digits.
public List<Integer> grayCode(int n) {
List<Integer> ret = new LinkedList<>();
ret.add(0);
for (int i = 0; i < n; i++) {
int size = ret.size();
for (int j = size - 1; j >= 0; j--)
ret.add(ret.get(j) + size);
}
return ret;
}
void generateGrayarr(int n){ // base case if (n <= 0) return; // 'arr' will store all generated codes vector<string> arr; // start with one-bit pattern arr.push_back("0"); arr.push_back("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 arr[] in reverse // order. Nor arr[] has double number of codes. for (j = i-1 ; j >= 0 ; j--) arr.push_back(arr[j]); // append 0 to the first half for (j = 0 ; j < i ; j++) arr[j] = "0" + arr[j]; // append 1 to the second half for (j = i ; j < 2*i ; j++) arr[j] = "1" + arr[j]; } // print contents of arr[] for (i = 0 ; i < arr.size() ; i++ ) cout << arr[i] << endl;}
For example, given n = 2, return
[0,1,3,2]. Its gray code sequence is:00 - 0 01 - 1 11 - 3 10 - 2
When n=3:
000
001
011
010
110
111
101
100
From: http://www.darrensunny.me/leetcode-gray-code/
We can construct a gray code sequence of length
public ArrayList<Integer> grayCode(int n) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (n < 0) // Invalid input
return result;
result.add(0);
if (n == 0) // No bit
return result;
result.add(1); // With one bit
// Iteratively contruct the grey code of n bits on that of n-1 bits
// gc(n) = gc(n-1) ... gc'(n-1)+2^(n-1), where
// gc'(n-1) means the reverse sequence of gc(n-1), and +2^(n-1) means adding
// 2^(n-1) to each number in the sequence
for (int i = 2; i <= n; i++) {
int size = result.size();
for (int j = size-1; j >= 0; j--)
result.add(result.get(j)+(1<<(i-1)));
}
return result;
}
vector<int> grayCode(int n) {
vector<int> ret;
int size = 1 << n;
for(int i = 0; i < size; ++i)
ret.push_back((i >> 1)^i);
return ret;
}
X. DFS
Gray Code | 生成相邻两个数只有1位不同的序列，每个数有n bit
public ArrayList<Integer> grayCode(int n) {
if (n == 0) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(0);
return list;
}
return getGrayCode(n - 1);
}
private ArrayList<Integer> getGrayCode(int pos) {
if (pos == 0) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(0);
list.add(1);
return list;
}
ArrayList<Integer> result = new ArrayList<Integer>();
ArrayList<Integer> startsWithZero = getGrayCode(pos - 1);
ArrayList<Integer> startsWithOne = new ArrayList<Integer>();
for (int i = startsWithZero.size() - 1; i >= 0; i--) {
startsWithOne.add(startsWithZero.get(i) + (1 << pos));
}
result.addAll(startsWithZero);
result.addAll(startsWithOne);
return result;
}
https://leetcode.com/discuss/73590/java-easy-version-to-understandpublic static List<Integer> grayCode(int n) { if (n < 0) return new ArrayList<Integer>(); if (n == 0) { List<Integer> list = new ArrayList<Integer>(); list.add(0); return list; } List<Integer> tmp = grayCode(n - 1); List<Integer> result = new ArrayList<Integer>(tmp); int addNumber = 1 << (n - 1); for (int i = tmp.size() - 1; i >= 0; i--) { result.add(addNumber + tmp.get(i)); } return result; }
EPI Solution: Compute a Gray code GrayCode.java
public static List<Integer> grayCode(int numBits) {if (numBits == 0) {
return Arrays.asList(0);
}
if (numBits == 1) {
return Arrays.asList(0, 1);
}
// These implicitly begin with 0.
List<Integer> grayCodeNumBitsMinus1 = grayCode(numBits - 1);
// Prepend 1 to entries in grayCodeNumBitsMinus1.
int leadingBitOne = 1 << (numBits - 1);
List<Integer> reflection = new ArrayList<>();
// Process in reverse order to achieve reflection of grayCodeNumBitsMinus1.
for (int i = grayCodeNumBitsMinus1.size() - 1; i >= 0; --i) {
reflection.add(leadingBitOne + grayCodeNumBitsMinus1.get(i));
}
List<Integer> result = new ArrayList<>(grayCodeNumBitsMinus1);
result.addAll(reflection);
return result;
}
Also refer to http://www.darrensunny.me/leetcode-gray-code/
http://www.programering.com/a/MDO0kDMwATM.html
Gray code to binary number
Read full article from 水中的鱼: [LeetCode] Gray Code 解题报告
