3.3 用Gray码的顺序列出一个集合的所有子集
///gary 码就是相邻两个集合中的元素里，只有一个不同。如0001 0011
1 // Question3_3.cpp : Defines the entry point for the console application.
2 //
3
4 #include <iostream>
5 #include <bitset>
6 #include <cmath>
7 #include <stack>
8
9 //#include "stdafx.h"
10 using namespace std;
11
12 const int bitNum = 4;
13 int temp = 16;
14 const int setNum = 16; //pow(2, bitNum);
15
16 struct itemData
17 {
18 bitset<bitNum> item;
19 int child;
20 };
21
22 int getChildNum(bitset<bitNum> curState, bitset<setNum> setTag);
23 bitset<bitNum> getChildIndex(bitset<bitNum> curState, bitset<setNum> setTag, int child);
24
25 void main(void)
26 {
27 itemData curData;
28 stack<itemData> states;
29 bitset<bitNum> curState;
30 bitset<setNum> setTag;
31
32 setTag.set(); // 1111111
.. means the states can be used
33 curState.reset(); // initialize as 000000. this is the scratch line
34 setTag.reset(curState.to_ulong()); // 0: used 1:unused
35 curData.child = getChildNum(curState, setTag);
36 curData.item = curState;
37 states.push(curData);
38
39 int child;
40 while(setTag.to_ulong() != 0) // not ended
41 {
42 curData = states.top();
43 child = curData.child;
44 curState = curData.item;
45 if( child == 0 )
46 {
47 states.pop();
48 setTag.set(curData.item.to_ulong()); //set this state be unused
49 } else {
50 curData.child--;
51 states.pop();
52 states.push(curData);
53 curState = getChildIndex(curState, setTag, child);
54 setTag.reset(curState.to_ulong()); // set this state be used
55
56 curData.child = getChildNum(curState, setTag);
57 curData.item = curState;
58 states.push(curData);
59 }
60 }
61 int total = 0;
62 while(!states.empty())
63 {
64 cout << states.top().item << "\n";
65 total++;
66 states.pop();
67 }
68 cout << total <<" right?\n";
69 }
70
71 int getChildNum(bitset<bitNum> curState, bitset<setNum> setTag)
72 {
73 bitset<bitNum> temp;
74 int child = 0;
75 for(int i = 0; i < curState.size(); i++)
76 {
77 temp = curState;
78 temp.flip(i);
79 if(setTag.test(temp.to_ulong()))
80 {
81 child++;
82 }
83 }
84 return child;
85 }
86
87 bitset<bitNum> getChildIndex(bitset<bitNum> curState, bitset<setNum> setTag, int child)
88 {
89 bitset<bitNum> temp;
90 for(int i = 0; i < curState.size(); i++)
91 {
92 temp = curState;
93 temp.flip(i);
94 if(setTag.test(temp.to_ulong()))
95 {
96 child--;
97 if(child == 0)
98 {
99 return temp;
100 }
101 }
102 }
103 }