全排列

對(duì)于全排列中的一般問(wèn)題則是根據(jù)字典序從小到大輸出指定數(shù)量或者序列的全排列。一個(gè)簡(jiǎn)單的問(wèn)題則是：指定n個(gè)整數(shù)，根據(jù)字典序從小到大輸出這n個(gè)整數(shù)的全排列。

從遞歸的角度去思考，對(duì)于這一問(wèn)題我們可以看成首先輸出以1開(kāi)頭的所有排列，然后輸出以2開(kāi)頭的排列，...，輸出以n為開(kāi)頭的排列。這樣便可將所有的排列都列舉出來(lái)。

現(xiàn)在假設(shè)p保存一個(gè)n位的排列。不妨假設(shè)已經(jīng)填充好了p[1]_{p[index-1]位，現(xiàn)在正準(zhǔn)備填充p[index]。此時(shí)，則需要枚舉1}n，如果當(dāng)前枚舉的數(shù)字x已經(jīng)被填充過(guò)，即在p[1]~p[index-1]中（如果使用hash來(lái)表示是否填充，則是hash[x]=true）則對(duì)x++，使用下一數(shù)字填充，如果x沒(méi)有被填充過(guò)，則把當(dāng)前的index位設(shè)置為填充x，同時(shí)hash[x]設(shè)置為true。然后轉(zhuǎn)到index+1對(duì)下一個(gè)進(jìn)行填充。當(dāng)遞歸完成時(shí)，由于當(dāng)前位可能還需嘗試其它填充，所以需要對(duì)當(dāng)前位還原。

實(shí)現(xiàn)代碼

#include<cstdio>
#include<cstring>

//p存儲(chǔ)當(dāng)前排列,hash記錄x是否已經(jīng)在p中 
int n, p[11], hash[11] = {false};

//當(dāng)前處理排列的第index位 
void generateP(int index){
    //遞歸邊界，已經(jīng)處理完排列的n個(gè)位則進(jìn)行輸出 
    if(index == n+1){
        for(int i = 1; i <= n; i++)
            printf("%d", p[i]);
        printf("\n");
        return;
    }
    //對(duì)index位嘗試n個(gè)數(shù)的填充，滿足條件則進(jìn)行填充并轉(zhuǎn)到下一位 
    for(int x = 1; x <= n; x++){
        //如果x不在p中則表示未被使用過(guò)，即可用于填充 
        if(hash[x] == false){
            p[index] = x;
            hash[x] = true;
            generateP(index+1);
            //由于對(duì)當(dāng)前位還需進(jìn)行其他填充，所以需要進(jìn)行重置。表示未填充過(guò) 
            hash[x] = false;
        }
    }
}
int main(){
    //設(shè)置為產(chǎn)生4的全排列 
    n = 4;
    //從1開(kāi)始填充 
    generateP(1);
    return 0;
}

n皇后問(wèn)題

n皇后問(wèn)題指在一個(gè)nn的棋盤(pán)中放置n個(gè)皇后，使得這n個(gè)皇后兩兩均不在同一行，同一列以及同一對(duì)角線上，并求出合法的方案數(shù)。對(duì)于這個(gè)問(wèn)題如果采用組合數(shù)的方式進(jìn)行枚舉，即nn的格子中選擇n個(gè)格子，其枚舉量是相當(dāng)大的，當(dāng)n變大時(shí)其時(shí)間復(fù)雜度是無(wú)法接受的。

因此可以換個(gè)思路，考慮每行只能放一個(gè)皇后，每列只能放一個(gè)皇后，那么如果把n列的皇后所在的行號(hào)依次寫(xiě)出，那么就會(huì)是1~n的一個(gè)排列。于是在這樣的思路下就只需要枚舉n個(gè)數(shù)的所有排列，然后查看每個(gè)排列的放置是否合法，統(tǒng)計(jì)合法的方案數(shù)便可。而在合法判斷時(shí)，則只需要對(duì)其放置是否存在有同一對(duì)角線的情況。

實(shí)現(xiàn)

#include<cstdio>
#include<cstring>
#include<cmath> 

//p存儲(chǔ)當(dāng)前排列,hash記錄x是否已經(jīng)在p中 
int count = 0; 
int n, p[11], hash[11] = {false};

//當(dāng)前處理排列的第index位 
void generateP(int index){
    //遞歸邊界，已經(jīng)處理完排列的n個(gè)位則進(jìn)行輸出 
    if(index == n+1){
        bool flag = true;
        //遍歷任意兩個(gè)皇后 
        for(int i = 1; i <= n; i++){
            for(int j = i+1; j <= n; j++)
                //如果在同一對(duì)角線 
                if(abs(i-j) == abs(p[i]-p[j]))
                    flag = false;//不合法 
        }
        if(flag) count++;//當(dāng)前方法合理，則count加1 
        return ;
    }
    //對(duì)index位嘗試n個(gè)數(shù)的填充，滿足條件則進(jìn)行填充并轉(zhuǎn)到下一位 
    for(int x = 1; x <= n; x++){
        //如果x不在p中則表示未被使用過(guò)，即可用于填充 
        if(hash[x] == false){
            p[index] = x;
            hash[x] = true;
            generateP(index+1);
            //由于對(duì)當(dāng)前位還需進(jìn)行其他填充，所以需要進(jìn)行重置。表示未填充過(guò) 
            hash[x] = false;
        }
    }
}
int main(){
    //設(shè)置為產(chǎn)生4的全排列 
    n = 8;
    //從1開(kāi)始填充 
    generateP(1);
    printf("%d皇后的方案數(shù)為：%d\n", n, count);
    return 0;
}