C实现排列组合

排列的定义：从n个不同元素中，任取m(m≤n,m与n均为自然数,下同）个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 A(n,m)表示。

C实现全排列代码如下：

//全排列
void permutation(int *array,int start,int end){
    int temp;
    int i=0;
    if(start>end)
        return;
    if(start<end){
        permutation(array, start+1, end);
        for(i=start+1;i<=end;i++){
            temp=array[start];
            array[start]=array[i];
            array[i]=temp;
            permutation(array, start+1, end);
            temp=array[start];
            array[start]=array[i];
            array[i]=temp;
        }
    }else{
        for(i=0;i<=end;i++){
            printf("%d ",array[i]);
        }
        printf("\n");
    }
}

测试用例如下：

int main(void){
    int i[5]={1,3,4,2,5};
    permutation(i,0,4);
    return 0;
}

运行结果如下：

1 3 4 2 5 
1 3 4 5 2 
1 3 2 4 5 
1 3 2 5 4 
1 3 5 2 4 
1 3 5 4 2 
1 4 3 2 5 
1 4 3 5 2 
1 4 2 3 5 
1 4 2 5 3 
1 4 5 2 3 
1 4 5 3 2 
1 2 4 3 5 
1 2 4 5 3 
1 2 3 4 5 
1 2 3 5 4 
1 2 5 3 4 
1 2 5 4 3 
1 5 4 2 3 
1 5 4 3 2 
1 5 2 4 3 
1 5 2 3 4 
1 5 3 2 4 
1 5 3 4 2 
3 1 4 2 5 
3 1 4 5 2 
3 1 2 4 5 
3 1 2 5 4 
3 1 5 2 4 
3 1 5 4 2 
3 4 1 2 5 
3 4 1 5 2 
3 4 2 1 5 
3 4 2 5 1 
3 4 5 2 1 
3 4 5 1 2 
3 2 4 1 5 
3 2 4 5 1 
3 2 1 4 5 
3 2 1 5 4 
3 2 5 1 4 
3 2 5 4 1 
3 5 4 2 1 
3 5 4 1 2 
3 5 2 4 1 
3 5 2 1 4 
3 5 1 2 4 
3 5 1 4 2 
4 3 1 2 5 
4 3 1 5 2 
4 3 2 1 5 
4 3 2 5 1 
4 3 5 2 1 
4 3 5 1 2 
4 1 3 2 5 
4 1 3 5 2 
4 1 2 3 5 
4 1 2 5 3 
4 1 5 2 3 
4 1 5 3 2 
4 2 1 3 5 
4 2 1 5 3 
4 2 3 1 5 
4 2 3 5 1 
4 2 5 3 1 
4 2 5 1 3 
4 5 1 2 3 
4 5 1 3 2 
4 5 2 1 3 
4 5 2 3 1 
4 5 3 2 1 
4 5 3 1 2 
2 3 4 1 5 
2 3 4 5 1 
2 3 1 4 5 
2 3 1 5 4 
2 3 5 1 4 
2 3 5 4 1 
2 4 3 1 5 
2 4 3 5 1 
2 4 1 3 5 
2 4 1 5 3 
2 4 5 1 3 
2 4 5 3 1 
2 1 4 3 5 
2 1 4 5 3 
2 1 3 4 5 
2 1 3 5 4 
2 1 5 3 4 
2 1 5 4 3 
2 5 4 1 3 
2 5 4 3 1 
2 5 1 4 3 
2 5 1 3 4 
2 5 3 1 4 
2 5 3 4 1 
5 3 4 2 1 
5 3 4 1 2 
5 3 2 4 1 
5 3 2 1 4 
5 3 1 2 4 
5 3 1 4 2 
5 4 3 2 1 
5 4 3 1 2 
5 4 2 3 1 
5 4 2 1 3 
5 4 1 2 3 
5 4 1 3 2 
5 2 4 3 1 
5 2 4 1 3 
5 2 3 4 1 
5 2 3 1 4 
5 2 1 3 4 
5 2 1 4 3 
5 1 4 2 3 
5 1 4 3 2 
5 1 2 4 3 
5 1 2 3 4 
5 1 3 2 4 
5 1 3 4 2

组合的定义：从n个不同元素中，任取m(m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m) 表示。

C实现组合代码如下：

#define N 5
//组合,C(num,m)
void combination(int *array,int start,int num,int m){
    static int queue[N];
    static int top;
    int i;
    if(start>num)
        return;
    if(top==m){
        for(i=0;i<m;i++){
            printf("%d ",queue[i]);
        }
        printf("\n");
        return;
    }
    queue[top++] = array[start];
    combination(array,start+1,num,m);
    top--;
    combination(array,start+1,num,m);
}

测试用例如下：

int main(void){
    int i[N]={1,3,4,2,5};
    combination(i,0,5,2);
    return 0;
}

运行结果如下：

1 3 
1 4 
1 2 
1 5 
3 4 
3 2 
3 5 
4 2 
4 5 
2 5