枚舉排列

生成1~n的排列
我們嘗試用遞歸的思想解決：先輸出以1開頭的排列（這一步是遞歸調(diào)用），然后輸出以2開頭的排列（又是遞歸調(diào)用），接著是以3為開頭的排列.....最后才是以n開頭的排列。
以1開頭的排列的特點(diǎn)是：第一位是1，后面是2~9的排列。根據(jù)字典序的定義，這些2~9的排列也必須按照字典序排列。換句話說，需要“按照字典序輸出2~9的排列”，不過需要注意的是，在輸出時，每個排列的最前面要加上“1”。這樣一來，所設(shè)計(jì)的遞歸偽碼如下：
void print_permutation(序列A，集合S){
if(S為空) 輸出序列A；
else 按照從小到大的順序依次考慮S的每個元素V{
print_permutation(在A末尾填加V后得到的新序列，S-{V}）；}
}
下面考慮程序?qū)崿F(xiàn)。不難想到用數(shù)組表示序列A，而集合S根本不用保存。因?yàn)?，它可以由序列A完全確定——A中沒有出現(xiàn)的元素都可以選。同時，我們還需要一個參數(shù)記錄當(dāng)前需要確定的位置cur,代碼如下：

#include"stdio.h"
#include"stdlib.h"
void print_permutation(int *A,int n,int cur){
    if(cur==n){
        for(int i=0;i<n;i++)
        printf("%3d",A[i]);
        printf("\n");
        return;
    }
    else{
        for(int i=1;i<=n;i++){
            int k=1;
            for(int j=0;j<cur;j++){
                if(A[j]==i){
                    k=0;
                    break;
                }
            }
            if(k){
                A[cur]=i;
                print_permutation(A,n,cur+1);
            }
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    int *A=(int *)malloc(sizeof(int)*n);
    print_permutation(A,n,0);
    free(A);
    return 0;
}
由于小編水平有限，歡迎讀者發(fā)現(xiàn)錯誤并指正。
下期，小編將帶來如何實(shí)現(xiàn)型如“1 1 1”序列的全排列