格雷码 (Gray code)

格雷码是任意两个相邻数的代码只有一位二进制数不同的编码

例如 3 位格雷码为

000
001
011
010
110
111
101
100

生成格雷码的代码为

#include <iostream>
#include <vector>


// 产生 n 位格雷格雷码
//
// 采用方法为镜射构建法
// n 位格雷码可由 n - 1 位格雷码得到
//
// 只需在 n - 1 位格雷码的前面加上 "0", 整体再加上
// 将 n - 1 位格雷码逆序之后在前面加上 "1"
//
// 例如：
// 0    00    000
// 1    01    001
//      11    011
//      10    010
//            110
//            111
//            101
//            100
std::vector<std::string> StringGrayCode(int n)
{
    if (n == 1) {
        return std::vector<std::string> {"0", "1"};
    }

    std::vector<std::string> gray_code_old = StringGrayCode(n - 1);
    std::vector<std::string> gray_code_new{};
    for (auto per_gray_code : gray_code_old) {
        gray_code_new.push_back("0" + per_gray_code);
    }
    for (auto p_per_gray_code = gray_code_old.rbegin();
            p_per_gray_code != gray_code_old.rend(); ++p_per_gray_code) {
        gray_code_new.push_back("1" + *p_per_gray_code);
    }

    return gray_code_new;
}

int main(int argc, char *argv[])
{
    for (auto per_gray_code : StringGrayCode(4)) {
        std::cout << per_gray_code << std::endl;
    }

    return 0;
}