简介
Gray Code,是几十年前贝尔实验室的科学家Frank Gray提出的一种编码方案,当时主要用于传输信号以防止出错。Gray Code 除了在通信,硬件设计领域中应用以外,在计算机相关科学的其他方面也有广泛的应用,例如按序产生集合的所有子集。
Gray Code实现按序产生集合的所有子集
子集的按序产生,这个概念很简单,举个例子,假设我们的集合为{a,b,c},那么按序产生的子集应该是:
空集 (000) —— 0(编号 从0开始按顺序排序)
a (100) —— 1
ab (110) —— 2
abc (111) —— 3
ac
b
bc
c
那么Gray Code是如何产生这样的序列的呢?
Gray Code的思想非常的巧妙,我们可以将所产生的子集编号(范围为0~2^n-1),第一个子集为空集(编号为0,是偶数)。在其后的每个子集由前一个子集来决定,如果前一个子集编号为偶数,那么则改变前一个子集的第一位(从左边数)的二进制值(0变成1或者1变成0)作为新的子集。如果前一个子集的编号为奇数,那么就将前一个子集二进制左边数第一个1后面的那位改变其值(0变成1或者1变成0)作为新的子集。
根据上面的Gray Code的思想,还是以集合{a,b,c}为例,第一个子集(000)的编号为0(偶数),推算出第二个子集是第一个子集改变左边数的第一位的数值所产生,为100,也就是a(只取为1的字符,a为最左边的字符对应100中的1)。那么根据第二个子集的编号1(奇数),推算出第三个子集是由第二个子集改变从左数第一个1后面那一位的值所产生(100->110),那么110对应的是ab。后面的子集都以此类推即可全部按顺序产生。
Gray Code非递归的C语言实现
以下代码在VS2008下调试通过
- int sum(int n)
- {
- if(1<=n) return n+sum(n-1);
- else return 0;
- }
-
- void gray(char *ptr)
- {
- int len=strlen(ptr);
- int num=(1<<len);
- // printf("num=%d \n",num);
- int i,j,k;
- int mod,tmp,mask,tmp1,tmp2;
- mask=1<<len-1;
- // printf("mask=%d \n",mask);
- mod=0;//(1<<len)-1;
- for(i=0;i<num-1;i++)
- {
- if(i%2==0)
- {
- tmp=mod&mask;
- // printf("tmp=%d ",tmp);
- if(0!=tmp) {mod=mod&(~mask);}
- else {mod=mod|(mask);}
- }
- else
- {
- tmp1=1<<(len-1);
- for(j=0;j<len;j++)
- {
- // printf(" in else");
- if(mod&tmp1) break;
- tmp1=tmp1>>1;
- // printf("tmp1=%d ",tmp1);
- }
- tmp1=tmp1>>1;
- // printf(">>1 tmp1=%d ",tmp1);
- if(tmp1!=0)
- {
- tmp=mod&tmp1;
- if(0!=tmp) {mod=mod&(~tmp1);}
- else {mod=mod|(tmp1);}
- }
- }
- tmp2=1<<len-1;
- for(k=0;k<len;k++)
- {
- if(mod&tmp2) printf("%c",ptr[k]);
- tmp2=tmp2>>1;
- }
- printf("\n");
- }
- }
-
- int main()
- {
- // printf(" result=%d ",sum(4));
- char *p="abcd";
- gray(p);
- system("pause");
- }