/* ------------------------------------------------------ *//* PROGRAM Subset Generation by Gray Code :               *//*    This program generates all possible subsets of a n  *//* elements set with Gray Code.  Simply speaking, the Gray*//* code of n bits is a sequence of n-bit strings such that*//* any two consecutive two bit strings have exactly one   *//* position in difference.  For example, for n = 3, the   *//* gray code generated is the sequence 000,001,010,011,   *//* 010,110,111,101 and 100.  Therefore each item of this  *//* sequence corresponds one subset as in the direct method*//*                                                        *//* Copyright Ching-Kuang Shene               July/05/1989 *//* ------------------------------------------------------ */ #include  <stdio.h>#include  <stdlib.h> #define   MAXSIZE         20#define   YES             1#define   LOOP            1 #define   FLIP_DIGIT(x)   x = ((x) == '0' ? '1' : '0')#define   FLIP(x)         x = (1 - (x)) void main(void){     char  digit[MAXSIZE];     int   position[MAXSIZE];     int   even;     int   n;     int   i, count = 0;     char  line[100];      printf("\nAll Subset Listing by Gray Code");     printf("\n===============================");     printf("\n\nNumber of Elements in Set Please --> ");     gets(line);     n = atoi(line);      printf("\n");            /* initialization           */     for (i = 0; i < n; i++) {          digit[i] = '0';          printf("0");     }     printf(" : {}\n");       /* the empty set            */      even = YES;     while (LOOP)  {          if (even)           /* for even positions:0,2,..*/               FLIP_DIGIT(digit[0]);  /* flip the 1st bit */          else {              /* for odd positions...     */               for (i = 0; i < n && digit[i] == '0'; i++)                    ;         /* find the first 1 bit     */               if (i == n-1) break; /* if it is the last..*/               FLIP_DIGIT(digit[i+1]); /* NO, flip its nbr*/          }          for (count = 0, i = n - 1; i >= 0; i--) {               printf("%c", digit[i]); /* print the bits  */               if (digit[i] == '1')    /* and collect pos */                    position[count++] = i + 1;          }          printf(" : {%d", position[count-1]);          for (i = count - 2; i >= 0; i--) /* print pos   */               printf(",%d", position[i]);          printf("}\n");          FLIP(even);         /* next will be odd(or even)*/     }}

评论