-
Notifications
You must be signed in to change notification settings - Fork 0
/
GrayCode.cpp
71 lines (61 loc) · 1.76 KB
/
GrayCode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <algorithm>
#include <bitset>
#include <string>
#include <vector>
#include "../utils/utils.hpp"
using std::bitset;
using std::cout;
using std::endl;
using std::for_each;
using std::make_move_iterator;
using std::reverse;
using std::string;
using std::vector;
/**
* @brief Generates recursively the binary reflected Gray code of order n
* @param n positive integer
* @output bit_strings a list of all generated bit strings of length n
* composing the Gray Code
*/
void brgc(const int n, vector<string> &bit_strings)
{
if (n <= 0)
throw "n should be a positive integer";
auto add_prefix = [](const string p, vector<string> &s) {
for (auto it = s.begin(); it != s.end(); it++)
*it = p + *it;
};
if (n == 1)
{
bit_strings.push_back("0");
bit_strings.push_back("1");
return;
}
else
{
//generate list L1 of bit strings of size n − 1 by calling BRGC(n − 1)
brgc(n - 1, bit_strings);
//copy list L1 to list L2 in reversed order
vector<string> l2 = bit_strings;
reverse(l2.begin(), l2.end());
//add 0 in front of each bit string in list L1
add_prefix("0", bit_strings);
//add 1 in front of each bit string in list L2
add_prefix("1", l2);
//append L2 to L1 to get list L
bit_strings.insert(
bit_strings.end(),
make_move_iterator(l2.begin()),
make_move_iterator(l2.end()));
}
}
int main()
{
vector<string> res;
int n = randint(1, 10);
brgc(n, res);
for_each(res.begin(), res.end(), [](string s) { cout << s << endl; });
cout << "the gray code for number " << n << " is: " << endl;
cout << "size: " << res.size() << endl;
}