组合算法 （来源与互联网） 
  本程序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标代表的数被选中，为0则没选中。
  首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。   
  然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。    
  当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得到了最后一个组合。
  例如求5中选3的组合：    
  1   1   1   0   0   //1,2,3
  1   1   0   1   0   //1,2,4
  1   0   1   1   0   //1,3,4
  0   1   1   1   0   //2,3,4
  1   1   0   0   1   //1,2,5
  1   0   1   0   1   //1,3,5
  0   1   1   0   1   //2,3,5
  1   0   0   1   1   //1,4,5
  0   1   0   1   1   //2,4,5
  0   0   1   1   1   //3,4,5

以下是实现：

#include<stdio.h>

#define MAXNUM 50

void init(int* pac, int n, int m);
void convert10To01(int* pac, int n, int m);

int main(){
 int i, count = 1;
 int n, m;
 int pac[MAXNUM];

 printf("please input two numbers(e.g.:5 3)\n");
 scanf("%d %d", &n, &m);
 printf("\n----------result-------------\n");

 init(pac, n, m);
 while(!end(pac, n, m)){
  convert10To01(pac, n, m);
  count++;

  for(i=0; i<n; i++){
   if(1 == pac[i])
    printf("%d ", i+1);
  }
  printf("\n");
 }

 printf("total: %d\n", count);
 return 0;
}

void init(int* pac, int n, int m){
 int i, j;
 
 for(i=0; i<n; i++){
  if(i < m)
   pac[i] = 1;
  else
   pac[i] = 0;
 }

 for(i=0; i<n; i++){
  if(1 == pac[i])
   printf("%d ", i+1);
 }
 printf("\n");
}

int end(int* pac, int n, int m){
 int i, j;

 for(i=n-m; i<n; ++i)
  if(pac[i] == 0) break;

 if(i >= n) return 1;
 else return 0;
}

void convert10To01(int* pac, int n, int m){
 int i, j;
 int count=0;

 for(i=0; i<n; i++){  
  if(1 == pac[i] && 0 == pac[i+1]){
   pac[i] = 0;
   pac[i+1] = 1;
   break;
  }
  if(1 == pac[i]) ++count;
 }

 for(j=0; j<i; j++){  
   if(j < count)
    pac[j] = 1;
   else
    pac[j] = 0;
 }
}

评论