C# -> 窮舉子集

如果有一個集合S = {0,1,2}
則S的所有子集為 :
1 : { }
2 : { 0 }
3 : { 1 }
4 : { 0 1 }
5 : { 2 }

6 : { 0 2 }     

7 : { 1 2 }     

8 : { 0 1 2 }     

我們可以用二進位的特性來實現...
以上例來說...從0~2^3 - 1的二進位制依序是...
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

000 可以看成0,1,2都不選，就是空集合
001 可以看成取0
......
111 可以看成0,1,2都選，就是S
C# code :

#include<stdio.h>

#include<stdlib.h>

int i=0,j=0,t=0,n=0 ;

void subsets(int n) 

{ 

  for (i=0;i<(1<<n);i++)   //利用位元運算從0 ~ 2^n - 1

  { 

    printf("%d : { ",i) ; 

    for (j=0,t=i;j<=n;j++,t>>=1) 

      if (t&1) 

        printf("%d ",j) ;  

    printf("}\n") ; 

  } 

}

int main()

{

  printf("Please enter a number which is smaller than 31\n") ;

  while(1)

  {

    n=31 ;

    while(n>30)scanf("%d",&n) ;

     subsets (n) ;

    printf("**********************************************\n") ;

  }

  //system("pause") ;

  return 0 ;

}

其中subsets，就是窮舉子集的函式。