定义一个数组，编程打印它的全排列

定义一个数组，编程打印它的全排列。比如定义：

#define N 3
int a[N] = { 1, 2, 3 };

则运行结果是：

$ ./a.out
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2 
1 2 3

程序的主要思路是：

1. 把第1个数换到最前面来（本来就在最前面），准备打印1xx，再对后两个数2和3做全排列。

2. 把第2个数换到最前面来，准备打印2xx，再对后两个数1和3做全排列。

3. 把第3个数换到最前面来，准备打印3xx，再对后两个数1和2做全排列。

可见这是一个递归的过程，把对整个序列做全排列的问题归结为对它的子序列做全排列的问题

解题过程：

   (1) 当 N = 1的时候，则直接打印数列即可。

   (2) 当 N = 2的时候，设数组为 [1, 2]

            打印a[0], a[1] （即1，2）

            交换a[0],a[1]里面的内容

            打印a[0],a[1]   （此时已变成了 [2, 1] ）

    (3) 当 N = 3的时候，数组为 [1, 2, 3]
          a. 把1放在 a[0] 的位置（原本也是如此，a[0] = a[0]），打印2,3的全排列（即a[1], a[2]的全排列）

                       1  2  3

                       1  3  2
         b.  把2放在a[0]的位置（这时候需要交换原数组的a[0]和a[1]），然后打印1, 3的全排列

                       2   1  3

                       2   3  1                        

                  打印完后再换回原来的位置，即1还是恢复到a[0]，2还恢复到a[1]的位置
         c.   把3放在a[0]的位置 （这时候需要交换的是原数组的a[0]和a[2]），然后打印1, 2的全排列
                      

                       3   2  1

                       3   1  2                        

                  打印完后再换回原来的位置，即1还是恢复到a[0]，3还恢复到a[2]的位置,
         至此全排列完成
 （4）N ＝ 4, 5, 6....的思路与此相同

#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);
}

void perm(int offset){
    int i, temp;
    if(offset == N-1){
        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;
}

完成了上述要求之后再考虑第二个问题：如果再定义一个常量M表示从N个数中取几个数做排列（N == M时表示全排列），原来的程序照如下方式修改：

#include <stdio.h>
#include <stdlib.h>

#define N 4
#define M 3

int a[N]; /* N个数 */
int temp[M]; /* 从N个数中选出的M个数 */

void perm(int, int); /* 排列 */
void swap(int, int); /* 交换两个数 */
void print(); /* 打印 */

int main(){
    int i;
    int start = 0;//起始位置
    int count = M;//排列到个数
    for(i = 0; i < N; i++){
        a[i] = i + 1;
    }
    perm(start, count);
}

void perm(int offset, int count){
    int i;
    if( count == 0 ){
        print();
        return;
    }else{
        for(i = offset; i < N; i++){
            temp[offset] = a[i];
            swap(offset, i);
            perm(offset+1, count-1);
            swap(offset, i);
        }
    }
}

void swap (int offset, int i){
    int another;
    another = a[offset];
    a[offset] = a[i];
    a[i] = another;
}

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

最后再考虑第三个问题：从N个数中取M个数做组合,

先看一个例子：
            C(5,3) = 10
               1 2 3
               1 2 4
               1 2 5
               1 3 4
               1 3 5
               1 4 5
               2 3 4
               2 3 5
               2 4 5
               3 4 5

分析
               1 | 2 3
               1 | 2 4
               1 | 2 5
               1 | 3 4
               1 | 3 5
               1 | 4 5 
              ------ C(4, 2)∵可以在{2, 3, 4, 5}中挑2个出来。

               2 | 3 4
               2 | 3 5
               2 | 4 5 
              ------ C(3, 2)∵可以在{3, 4, 5}中挑2个出来。

               3 | 4 5 
              ------ C(2, 2)∵只能在{4, 5}中挑2个出来。
               
这样就很容易写出递归算法来：

Algorithm combination（n, k, A[l..n+l-1]）
if k = 0
   print ary[1..k]
else
   for i←1 to n-k+1
       ary[index++] = A[l+i-1]
       combination（n-i, k-1, A[l+i..n+l-1]）
       --index
   endfor

源代码如下：

#include <stdio.h>
#include <stdlib.h>

#define N 4
#define M 3

int a[N]; /* N个数 */
int temp[M]; /* 从N个数中选出的M个数 */
int top;

void comb(int, int); /* 组合 */
void swap(int, int); /* 交换两个数 */
void print(); /* 打印 */

int main(){
    int i;
    int start = 0;//起始位置
    int count = M;//排列到个数
    for(i = 0; i < N; i++){
        a[i] = i + 1;
    }
    comb(start, count);
}

void comb(int offset, int count){
    int i;
    if( count == 0 ){
        print();
        return;
    }else{
        for(i = offset; i < N - count + 1; i++){
            temp[top++] = a[i];
            comb(i+1, count-1);
            --top;
        }
    }
}

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