一种可行的算法：
由于属性泛化后，一个泛化的假设可以对应多个具体假设。
把所有假设按三属性泛化，二属性泛化，一属性泛化，具体属性排序(这样可以保证排在后面的假设不会包含前面的任何一个假设，所以省略了一些包含判断)，进行循环枚举，按顺序遍历所有假设组合248种可能(当然绝大部分都提前结束了，不会是那么夸张的量级，虽然也不低)：
- 使用栈来实现非递归，如果当前假设还有没被析合式所包含的具体假设，则认为可以入栈，并当前栈大小的长度计数加1，并继续扫描。
- 如果当前扫描已经到了最后一个假设，或者所有具体假设已经被全部包含，则退栈。
- 循环结束条件：当最后一个假设作为第一个压入栈的元素时，认为已经遍历结束。
由于一共有18种具体假设，可以用一个32位整型(变量为hypos_cur)的后18位来表示每一个具体假设。用1表示具体假设没被包含，用0表示具体假设已经被析合式包含。初始的析合式为空，可以设初试值为0X3FFFF。每个假设也对应一个32位整型(假设变量为hypo_const),代表着它所对应了哪些具体假设，如果它包含了某种具体假设，则该位为1。
- 判断析合式是否包含了全部的具体假设：hypos_cur=0。
- 判断该假设是否已经被析合范式包含:用hypo_const与hypos_cur做与运算(结果用hypo_tmp表示)，如果为0表示已经被包含(判断该假设是否包含了当前的析合式:用hypo_const与hypos_cur做或运算，如果为0X3FFFFF，则认为该假设包含了当前析合式，但由于前面对所有假设做了排序，不可能出现这种情况，所以可以省略该判断)。
- 当某个假设加入析合范式后(入栈)用hypos_cur与hypo_tmp做异或运算，来更改析合式所包含的具体假设。
- 出栈时再次用hypos_cur与hypo_tmp做异或，回到加入该假设前的情况。
- 因为是指数级遍历的算法，所以很慢
下面将直接贴上代码，供参阅讨论：
1 #include <vector> 2 3 #include <stack> 4 5 using namespace std; 6 7 8 9 //按泛化程度排序，保证排在后面的假设不会不会包含前面的任何一个假设 10 11 static const char list[] = { 12 13 0,0,0, 14 15 0,0,1,0,0,2,0,0,3,0,1,0,0,2,0,0,3,0,1,0,0,2,0,0, 16 17 0,1,1,0,1,2,0,1,3,0,2,1,0,2,2,0,2,3,0,3,1,0,3,2,0,3,3, 18 19 1,0,1,1,0,2,1,0,3,2,0,1,2,0,2,2,0,3, 20 21 1,1,0,1,2,0,1,3,0,2,1,0,2,2,0,2,3,0, 22 23 1,1,1,1,1,2,1,1,3,1,2,1,1,2,2,1,2,3,1,3,1,1,3,2,1,3,3, 24 25 2,1,1,2,1,2,2,1,3,2,2,1,2,2,2,2,2,3,2,3,1,2,3,2,2,3,3 26 27 }; 28 29 30 31 //用来派生的抽象类 32 33 class hypos { 34 35 public: 36 37 virtual int insert(int cur) = 0; 38 39 }; 40 41 42 43 //单个的假设类 44 45 /* 46 47 hypo_const 假设对应的具体假设集合 48 49 */ 50 51 class hypo :public hypos { 52 53 public: 54 55 hypo(int a, int b, int c) { 56 57 hypo_const = 0; 58 59 vector<char> p[3]; 60 61 if (a == 0) { 62 63 p[0].push_back(1); 64 65 p[0].push_back(2); 66 67 } 68 69 else 70 71 p[0].push_back(a); 72 73 if (b == 0) { 74 75 p[1].push_back(1); 76 77 p[1].push_back(2); 78 79 p[1].push_back(3); 80 81 } 82 83 else 84 85 p[1].push_back(b); 86 87 if (c == 0) { 88 89 p[2].push_back(1); 90 91 p[2].push_back(2); 92 93 p[2].push_back(3); 94 95 } 96 97 else 98 99 p[2].push_back(c); 100 101 for (unsigned int i = 0;i < p[0].size();i++) 102 103 for (unsigned int j = 0;j < p[1].size();j++) 104 105 for (unsigned int k = 0;k < p[2].size();k++) 106 107 hypo_const |= (1 << (p[0][i] * 9 + p[1][j] * 3 + p[2][k] - 13)); 108 109 } 110 111 112 113 //判断是否要加入到析合式 如果还有具体假设没被包含，则加入 114 115 int insert(int cur) { 116 117 return (hypo_const & cur); 118 119 }; 120 121 122 123 private: 124 125 int hypo_const; 126 127 }; 128 129 130 131 //用于压入栈的派生类 用来实现非递归 132 133 /* 134 135 hypo_tmp 记录这个假设入栈时，带入了哪些具体假设，出栈时要还原 136 137 ptr 记录入栈时的位置 138 139 */ 140 141 class hypo_ss :public hypos { 142 143 public: 144 145 hypo_ss(int _ptr,int tmp){ 146 147 hypo_tmp = tmp; 148 149 ptr = _ptr; 150 151 } 152 153 int insert(int cur) { 154 155 return 0; 156 157 }; 158 159 int hypo_tmp; 160 161 int ptr; 162 163 }; 164 165 166 167 //用来循环遍历的类 168 169 /* 170 171 sum 各个长度的析合式各有多少种可能 172 173 ss 用来实现非递归的栈 174 175 hypos_cur 当前没被包含的具体假设 初始值为0X3FFFF 176 177 hyposs 48个假设集合 178 179 */ 180 181 class Traversal :public hypos { 182 183 public: 184 185 Traversal() { 186 187 hypos_cur = 0x3ffff; 188 189 for(int i=0;i<48;i++) 190 191 hyposs.push_back(hypo(list[3*i], list[3*i+1], list[3*i+2])); 192 193 } 194 195 196 197 //循环顺序遍历的主体 198 199 //cur 初试的位置 设为0 200 201 int insert(int cur) { 202 203 //当前指向的位置 204 205 int ptr = cur; 206 207 while (1) { 208 209 //退出条件 当最后一个假设作为第一个入栈的元素 表示遍历完成 210 211 if (ptr > 47 && !ss.size()) break; 212 213 //回退条件 扫描到最后或者所有具体假设都被包含 214 215 if (hypos_cur == 0 || ptr>47) { 216 217 hypo_ss hypo_tmp = ss.top(); 218 219 hypos_cur ^= hypo_tmp.hypo_tmp; 220 221 ptr = hypo_tmp.ptr + 1; 222 223 ss.pop(); 224 225 continue; 226 227 } 228 229 230 231 //入栈条件 如果该假设还有未被包含的具体假设 则入栈，并当前栈大小的计数加1 232 233 if (int tmp =hyposs[ptr].insert(hypos_cur)) { 234 235 hypos_cur ^= tmp; 236 237 ss.push(hypo_ss(ptr, tmp)); 238 239 if (sum.size() < ss.size()) 240 241 sum.push_back(0); 242 243 sum[ss.size() - 1]++; 244 245 } 246 247 ptr++; 248 249 } 250 251 return 1; 252 253 }; 254 255 //输出各个长度的可能数 256 257 void print() { 258 259 for (unsigned int i = 0;i < sum.size();i++) 260 261 printf("length %d : %d\n", i + 1, sum[i]); 262 263 } 264 265 private: 266 267 vector<int> sum; 268 269 stack<hypo_ss> ss; 270 271 int hypos_cur; 272 273 vector<hypo> hyposs; 274 275 }; 276 277 278 279 int main() 280 281 { 282 283 Traversal traversal; 284 285 traversal.insert(0); 286 287 traversal.print(); 288 289 system("pause"); 290 291 return 0; 292 293 }
