1.组合

如果从N个数中取M个数进行组合，该怎么编程实现呢？

例如从1，2，3，4中选取两个数进行组合，得到下列组合结果：

1，2

1，3

1，4

2，3

2，4

3，4

这里编程我们考虑递归算法，两个数组，a存储给定数组，b存储组合的元素，算法的核心是从a中逆着取元素组成数组b.

程序如下：

#include<stdio.h>
#define N 4
#define M 2

//全局变量，a为给定数组，b为存储组合的数组
int a[N];
int b[M];

//函数声明
void comb(int,int);
void print();

//打印数组b
void print()
{
    int i;
    for(i=0;i<M;i++) {
        printf("%d ",b[i]);
    }
    printf("\n");
}

//组合，递归方式
void comb(int n,int m)
{
    int i;
    if(m==0) {
        print();
        return;
    } else {
        for(i=n-1;i>=0;--i) {
            b[m-1]=a[i];
            comb(i,m-1);
        }
    }
}

int main()
{
    int i;
    for(i=0;i<N;i++)
        a[i]=i+1;
    comb(N,M);
    return 0;
}

2.全排列

假设现在给定数组1,2,3，其全排列如下所示：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

编程时，同样，还是采用递归的方法。

#include <stdio.h>
#define N 3

int a[N];  //全局变量，数组

//函数声明
void perm(int); /*求数组的全排列 */
void print();
void swap(int, int);


//主函数
int main(){
    int i;
    for(i = 0; i < N; ++i){
        a[i] = i + 1;
    }
    perm(0);
    return 0;
}

//全排列函数
void perm(int offset){
    int i, temp;
    if(offset == N-1){  // BaseCase
        print();
        return;
    }else{
        for(i = offset;i < N; ++i){
            swap(i, offset);//交换前缀
            perm(offset + 1);//递归
            swap(i, offset);//将前缀换回来，继续做前一次排列
        }
    }
}

//打印数组
void print(){
    int i;
    for(i = 0; i < N; ++i)
        printf(" %d ",a[i]);
    printf("\n");
}   

//交换全局数组的两个指定元素
void swap(int i, int offset){
    int temp;
    temp = a[offset];
    a[offset] = a[i];
    a[i] = temp;
}

3.部分排列

例如从N个数中取出M个数，进行全排列。

#include<stdio.h>

#define N 4
#define M 2
int a[N];

void print()
{
    int i;
    for(i=0;i<M;++i) 
        printf(" %d ",a[i]);
    printf("\n");
}

void swap(int i,int j)
{
    int tmp=a[i];
    a[i]=a[j];
    a[j]=tmp;
}

void perm(int offset)
{
    int i;
    if(offset==M) {
        print();
        return;
    } else {
        for(i=offset;i<N;i++) {
           swap(i,offset);
           perm(offset+1);
           swap(i,offset);
        }
    }
}

int main()
{
    int i;
    for(i=0;i<N;i++)
        a[i]=i+1;
    perm(0);   
}

组合与排列

原文：http://my.oschina.net/zzw922cn/blog/520225