Skip to content

Instantly share code, notes, and snippets.

@vedantk
Created March 20, 2013 08:14
Show Gist options
  • Save vedantk/5203093 to your computer and use it in GitHub Desktop.
Save vedantk/5203093 to your computer and use it in GitHub Desktop.
Gray codes in c++
#include <vector>
#include <string>
#include <iostream>
using namespace std;
void gray(int n, vector<string>& code) {
if (n == 1) {
code.push_back(string("0"));
code.push_back(string("1"));
} else {
vector<string> prev;
gray(n - 1, prev);
for (size_t i = 0; i < prev.size(); ++i) {
code.push_back(string("0") + prev[i]);
}
/*
* The first version of this program had a subtle bug in it.
* Can you find it? Hint: will this loop ever terminate?
*
* for (size_t i = prev.size() - 1; i >= 0; --i) {
*/
for (long i = long(prev.size() - 1); i >= 0; --i) {
code.push_back(string("1") + prev[i]);
}
}
}
int main(int argc, char** argv) {
vector<string> code;
gray(8, code);
cout << "[";
for (size_t i = 0; i < code.size(); ++i) {
cout << code[i];
if (i != code.size() - 1) {
cout << ",";
}
}
cout << "]";
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment