热转印www.yxheatpress.com

公司网站模板http://qiyemoban.software8.co/

常用链接

统计

友情链接

最新评论

Gray Code实现按序产生集合的所有子集

简介

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下调试通过


  1. int sum(int n)  
  2. {  
  3.     if(1<=n) return n+sum(n-1);  
  4.     else return 0;  
  5. }  
  6.   
  7. void gray(char *ptr)  
  8. {  
  9.     int len=strlen(ptr);  
  10.     int num=(1<<len);  
  11. //    printf("num=%d  \n",num);  
  12.     int i,j,k;  
  13.     int mod,tmp,mask,tmp1,tmp2;  
  14.     mask=1<<len-1;  
  15.  //   printf("mask=%d  \n",mask);  
  16.     mod=0;//(1<<len)-1;  
  17.     for(i=0;i<num-1;i++)  
  18.     {  
  19.         if(i%2==0)  
  20.         {  
  21.             tmp=mod&mask;  
  22.  //           printf("tmp=%d  ",tmp);  
  23.             if(0!=tmp) {mod=mod&(~mask);}  
  24.             else {mod=mod|(mask);}  
  25.         }  
  26.         else  
  27.         {  
  28.             tmp1=1<<(len-1);  
  29.             for(j=0;j<len;j++)  
  30.             {  
  31. //                printf(" in else");  
  32.                 if(mod&tmp1) break;  
  33.                 tmp1=tmp1>>1;  
  34.  //               printf("tmp1=%d  ",tmp1);  
  35.             }  
  36.             tmp1=tmp1>>1;  
  37.  //           printf(">>1  tmp1=%d  ",tmp1);  
  38.             if(tmp1!=0)   
  39.             {  
  40.                 tmp=mod&tmp1;  
  41.                 if(0!=tmp) {mod=mod&(~tmp1);}  
  42.                 else {mod=mod|(tmp1);}  
  43.             }  
  44.         }  
  45.         tmp2=1<<len-1;  
  46.         for(k=0;k<len;k++)  
  47.         {  
  48.             if(mod&tmp2) printf("%c",ptr[k]);  
  49.             tmp2=tmp2>>1;  
  50.         }  
  51.         printf("\n");  
  52.     }  
  53. }  
  54.   
  55. int main()  
  56. {  
  57. //    printf("  result=%d ",sum(4));  
  58.     char *p="abcd";  
  59.     gray(p);  
  60.     system("pause");  
  61. }  

posted on 2012-10-29 17:08 不听话的 阅读(1087) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理