整理摘自 https://blog.csdn.net/icefire_tyh/article/details/52065626

若不考虑冗余:

属性1    属性2    属性3

   2           3            3

假设空间中有 3 * 4 * 4 + 1 = 49种假设。

在不考虑沉余的情况下,最多包含k个合取式来表达假设空间,显然k的最大值是49

但是其中包含了很多冗余的情况。

------------------------------------------------------

若考虑冗余的情况(忽略空集):

48种假设中:

1)具体假设:2 * 3 * 3 = 18

21个属性泛化: 3 * 3 + 2 * 3 + 2 * 3 = 21

                                     |          |           |

                                  1泛化  2泛化   3泛化

32个属性泛化:2 + 3 + 3 = 8

43个属性泛化:1

若考虑冗余,k最大取值为18.(若大于18,则必含有泛化假设,泛化会减少具体假设数目,假设数目将小于18,与大于18矛盾)

这时需要根据k取值的不同分清况讨论。

1k
= 1时,任选一种假设都可以作为一种没有沉余的假设,共48种。

2k
= 18时,就是18种具体属性假设的析取式,共1种。

31
< k < 18时,需要另加分析。

算法:

由于属性泛化后,一个泛化的假设可以对应多个具体假设。

把所有假设按三属性泛化,二属性泛化,一属性泛化,具体属性排序

(这样可以保证排在后面的假设不会包含前面的任何一个假设,所以省略了一些包含判断)

进行循环枚举,按顺序遍历所有假设组合2^48种可能(当然绝大部分都提前结束了,不会是那么夸张的量级,虽然也不低)

·
使用栈来实现非递归,如果当前假设还有没被析合式所包含的具体假设,则认为可以入栈,并且当前栈大小的长度计数加111,并继续扫描。

·
如果当前扫描已经到了最后一个假设,或者所有具体假设已经被全部包含,则退栈。

·
循环结束条件:当最后一个假设作为第一个压入栈的元素时,认为已经遍历结束。

细节设计:

a. 每个假设的表示:

每个假设对应一个32位整型(假设变量为hypo_const),代表着它所对应了哪些具体假设,如果它包含了某种具体假设,则该位为1

eg. 假设1
00 0000 0000 0000 0001

b. 析合式包含的假设的表示:

由于一共有18具体假设,可以用一个32位整型(变量为hypos_cur)的后18位来表示每一个具体假设。用1表示具体假设没被包含,用0表示具体假设已经被析合式包含。

初始的析合式为空,可以设初试值为0X3FFFF

c. 判断析合式是否包含了全部的具体假设:

hypos_cur=0

d. 判断该假设是否已经被析合范式包含:

hypo_tmp
= hypos_cur & hypo_const

hypo_tmp
= 1, 入栈,

hypo_tmp
= 0, 不入栈。

hypos_cur    hypo_const    hypo_tmp

          0                0                     0                -> 析合式已包含                             -> 不入栈

          0                1                     0                -> 析合式已包含                             -> 不入栈

          1                0                     0                -> 析合式未包含,假设未包含
-> 不入栈

          1                1                     1                ->
析合式未包含,假设包含      -> 入栈

e. 入栈的操作:

hypos_cur ^=
hypo_tmp

当某个假设加入析合范式后(入栈)hypos_curhypo_tmp做异或运算,来更改析合式所包含的具体假设。

若可以入栈,则假设对应位hypo_tmp
= 1, hypos_cur = 1, 异或运算后为0,表示析合式包含改假设。

采用异或运算的好处是,在出栈时,再次异或即可还原hypos_cur原状态。

f. 出栈的操作:

hypos_cur ^=
hypo_tmp

出栈时再次用hypos_curhypo_tmp做异或,回到加入该假设前的情况。

代码实现:

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <vector>
  5 #include <stack>
  6 using namespace std;
  7 
  8 // 0表示*泛化情况
  9 // 1 表示该属性下取第1种属性值,2,3同理
 10 // 每三个一组,如000:***;123:三种属性分别取第1,2,3个属性值
 11 // 一组中有几个0表示几属性泛化
 12 
 13 static const char list[] = {
 14     0,0,0,                                                                            
 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     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,
 17     1,0,1,1,0,2,1,0,3,2,0,1,2,0,2,2,0,3,
 18     1,1,0,1,2,0,1,3,0,2,1,0,2,2,0,2,3,0,
 19     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,
 20     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
 21 };
 22 
 23 class hypos {
 24 public:
 25     virtual int insert(int cur) = 0;  //基类中的纯虚函数
 26 };
 27 
 28 //单个的假设类
 29 // hypo_const 表示具体假设
 30 class hypo: public hypos
 31 {
 32 public:
 33     hypo(int a, int b, int c)
 34     {
 35         hypo_const = 0;
 36         vector<char> p[3];
 37         // a = 0 表示第一种取泛化属性,需要把其包含的1,2两种具体属性都存入p容器中
 38         if(a == 0)   
 39         {
 40             p[0].push_back(1);
 41             p[0].push_back(2);
 42         }
 43         else p[0].push_back(a);
 44 
 45         if(b == 0)
 46         {
 47             p[1].push_back(1);
 48             p[1].push_back(2);
 49             p[1].push_back(3);
 50         }
 51         else p[1].push_back(b);
 52 
 53         if(c == 0)
 54         {
 55             p[2].push_back(1);
 56             p[2].push_back(2);
 57             p[2].push_back(3);
 58         }
 59         else p[2].push_back(c);
 60 
 61         for(unsigned int i = 0; i < p[0].size();i++)
 62             for(unsigned int j = 0; j < p[1].size(); j++)
 63                 for(unsigned int k = 0; k < p[2].size(); k++)
 64                     // 最小 1 1 1:1*9+1*3+1 = 13
 65                     // 这里 -13为保证右移计数从0开始,每一种假设对应一位
 66                     // |= 表示按位或
 67                     // 对于每一种具体假设,基本只用一次 如 1 1 1 -> 0...01
 68                     // 对于有泛化的假设,则会用到如 1 1 0 
 69                     // 其p[2]位有1,2,3三种属性,需要将这三种假设对应位置为1
 70                     // 0...0 0001, 0...0 0010, 0...0 0100 按位或 = 0... 0 0111
 71                     hypo_const |= (1 << (p[0][i] * 9 + p[1][j] * 3 + p[2][k]) – 13);
 72 
 73     }
 74 
 75     int insert(int cur)
 76     {
 77         // 若 hypo_const & cur = 1,则可以入栈
 78         return (hypo_const & cur); 
 79     }
 80 
 81 private:
 82     int hypo_const;  //表示具体假设
 83 };
 84 
 85 // 用于压入栈的派生类 用来实现非递归
 86 // hypo_tmp 记录这个假设入栈时,带入了哪些具体假设,出栈时要还原 
 87 // ptr 记录入栈时的位置
 88 
 89 class hypo_ss: public hypos
 90 {
 91 public:
 92     hypo_ss(int _ptr, int tmp)
 93     {
 94         hypo_tmp = tmp;
 95         ptr = _ptr;
 96     }
 97 
 98     int insert(int cur)
 99     {   return 0;    }
100     
101     int hypo_tmp;
102     int ptr;
103 };
104 
105 // 用来循环遍历的类
106 // sum 各个长度的析合式各有多少种可能
107 // ss 用来实现非递归的栈 
108 // hypos_cur 当前没被包含的具体假设 初始值为0X3FFFF 
109 // hyposs 48个假设集合
110 
111 class Traversal : public hypos
112 {
113 public:
114     Traversal()
115     {
116         hypos_cur = 0x3ffff;
117         for(int i = 0; i < 48; ++i)
118         {
119             // 见list[] : (0,0,0), (0,0,1) …
120             // hypo(a, b, c) 表某个假设(属性分别为a,b,c)
121             hyposs.push_back(hypo(list[3 * i], list[3 * i + 1], list[3 * i + 2])); 
122         }
123     }
124     
125     //循环顺序遍历的主体 
126     //cur 初始的位置 设为0
127     int insert(int cur)
128     {
129         int ptr = cur;    //当前指向的位置
130         while(1)
131         {
132             //退出条件 当最后一个假设作为第一个入栈的元素 表示遍历完成
133             if(ptr > 47 && !ss.size()) break;
134 
135             //回退条件 扫描到最后或者所有具体假设都被包含 
136             if(hypos_cur == 0 || ptr > 47)
137             {
138                 hypo_ss hypo_tmp = ss.top();
139                 hypos_cur ^= hypo_tmp.hypo_tmp;    //出栈异或
140                 ptr = hypo_tmp.ptr + 1;
141                 ss.pop();
142                 continue;
143             }
144             
145             //入栈条件 如果该假设还有未被包含的具体假设 则入栈,
146             // 并当前栈大小的计数加1
147             if(int tmp = hyposs[ptr].insert(hypos_cur))
148             {
149                 hypos_cur ^= tmp;
150                 ss.push(hypo_ss(ptr, tmp));
151                 if(sum.size() < ss.size())
152                     sum.push_back(0);
153                 sum[ss.size() - 1]++;
154             }
155             ptr++;
156         }
157         return 1;
158     }
159     //输出各个长度的可能数
160     void print()
161     {
162         for(unsigned int i = 0; i < sum.size(); ++i)
163             printf("length %d : %d\n", i + 1, sum[i]);
164     }
165 
166 private:
167     vector<int> sum;
168     stack<hypo_ss> ss;
169     int hypos_cur;
170     vector<hypo> hyposs;
171 };
172 
173 int main()
174 {
175     Traversal traversal;
176     traversal.insert(0);
177     traversal.print();
178     system("pause");
179     return 0;
180 }
181 
182 /* Output:
183 length 1 : 48
184 length 2 : 931
185 length 3 : 10332
186 length 4 : 72358
187 length 5 : 342057
188 length 6 : 1141603
189 length 7 : 2773332
190 length 8 : 4971915
191 length 9 : 6543060
192 length 10 : 6175660
193 length 11 : 4003914
194 length 12 : 1676233
195 length 13 : 422676
196 length 14 : 61884
197 length 15 : 5346
198 length 16 : 435
199 length 17 : 27
200 length 18 : 1
201 sh: 1: pause: not found
202 */