证明:{1,2,3,n}的全部子集可以排成一条链,使得链上每相邻的集合恰差一个元素

Question

证明:{1,2,3,n}的全部子集可以排成一条链,使得链上每相邻的集合恰差一个元素

Answer 1

可以考虑这样一种处理办法：假设我们把集合的某个子集写成一个n元的数组（an,.a3,a2,a1).其中如果元素i在这个子集中出现了,那么ai就是1；i没有在子集中出现ai就是0.可以用由0,1组成的数组来表示所有子集.
下面生成满足要求的一个链：
（1）从（0,0,0,...,0),也就是空集开始.
（2）计算A=a1+a2+a3+.+an
（3）若A是一个偶数,则改变a1（从1变成0,或者从0变成1）；
若A是一个奇数,找到一个aj,aj右侧的所有数都是0,然后改变a（j+1）,其中如果a1是1,直接改变a2.
（4）经过（3）处理的数组标记为新的（an,...a3,a2,a1),再一次进入（2）当中,循环往复,直到数组为（1,0,0,.,0)为止,所有子集均被不重不漏地排列在了链当中.
举个5元数组的例子：00000,00001,00011,00010,00110,00111,00101,00100,01100,01101,01111,01110,01010,01011,01001,01000,11000,11001,11011,11010,11110,11111,11101,11100,10100,10101,10111,10110,10010,10011,10001,10000.
不重不漏.这种编码方式被称作“反射gray码”,由于相邻两个数组只相差一个元素,大大降低了计算机出错的几率