全排列方法

方法引入

我們若是想計算 1、2、3 的全排列，最易理解的方法就是利用三重回圈輸出

for(int i=1; i<=3; i++)
    for(int j=1; j<=3; j++)
        for(int k=1; k<=3; k++)
            if(i!=j && i!=k && j!=k)
                printf("%d %d %d\n", i, j, k);

然而如果我們想輸出任意階數的全排列呢?
這種方法顯然不合適

方法介紹

我們以撲克牌和盒子（垃圾桶）來模擬另一種方法

假設有 “一、二、三” 三個盒子和 “1、2、3” 三張撲克牌

首先將三張撲克牌順序拿在手中，每當站在一個盒子前面，都按一定的順序扔進去一張牌，一個盒子只能裝一張牌，我們約定一個順序：先放 1 號再放 2 號，最后放 3 號

首先我們站在一號盒子前，依照順序仍入 1 號撲克牌

之后向前走來到二號盒子前，按次序應放入 1 號撲克牌，可是，一號撲克牌已經不在手上了，于是我們放入 2 號撲克牌

放好之后再向前走來到三號盒子前，放入 3 號撲克牌

再次前進時發現沒有盒子了，這時三個盒子都放滿了，一種排列就完成了，即為 “1 2 3”

一種排列完成后，我們只能后退取回剛才放入的牌，于是退回三號垃圾桶 （盒子）取回 3 號牌（撿垃圾）

此時若想放入 3 號牌，構成的序列與之前序列一樣，沒有辦法只能繼續后退了，于是退回二號盒子取回 2 號牌

由于放 2 號牌的話與之前序列相同，我們只能放既定順序的下一張牌：3 號牌，按之前的步驟，“1 3 2” 就誕生了

接下來按照剛才的步驟去模擬，就會依次產生：“2 1 3”、“2 3 1”、“3 1 2”、“3 2 1”

代碼實作

首先，要按照順序放入1、2、3號撲克牌，這需要一一判斷

for(i=1; i<=n; i++)
{
    a[step] = i;        //將第i號撲克牌放到第step個盒子中
}

可是，如果一張撲克牌已經放到別的盒子中了，那手中就沒有這張撲克牌了，因此需要一個陣列 book 來標記手中的牌

for(i=1; i<=n; i++)
{
    if(!book[i])        //book[i]為0代表未放入盒子
    {
        a[step] = i;
        book[i] = 1;    //表示第i號牌已經不再手上了
    }
}

處理完了第 step 個盒子，接下來需要往下走處理第 step+1 個盒子，該如何做到呢？

其實方法和之前一樣，因此可以將上述步驟封裝成函式，用遞回的方法實作

void dfs(int step)      //step表示站在第幾個盒子前
{
    for(i=1; i<=n; i++)
    {
        if(!book[i])
        {
            a[step] = i;
            book[i] = 1;
            dfs(step+1);
            book[i] = 0;
        }
    }
}

注意上述代碼中的

book[i] = 0;

十分重要！！！
它的作用是退回的時候將撲克牌識訓，不然就無法進行下一次投放（扔垃圾）

然而上述代碼還是不完整的
我們需要在 step=n+1 的時候結束此次遞回，并輸出當前排列

void dfs(int step)
{
    if(step == n+1)
    {
        for(i=1; i<=n; i++)
            printf("%3d", a[i]);
        printf("\n");
        return;             //結束當前遞回即開始后退
    }
    for(i=1; i<=n; i++)
    {
        if(!book[i])
        {
            a[step] = i;
            book[i] = 1;
            dfs(step+1);
            book[i] = 0;
        }
    }
}

完整代碼

#include <stdlib.h>
#include <stdio.h>
int a[100001], n, book[100001];
void dfs(int step)
{
    int i;
    if(step==n+1)
    {
        for(i=1; i<=n; i++)
            printf("%d ", a[i]);
        printf("\n");
        return;
    }
    for(i=1; i<=n; i++)
    {
        if(!book[i])
        {
            a[step] = i;
            book[i] = 1;
            dfs(step+1);
            book[i] = 0;
        }
    }
}

int main()
{
    scanf("%d", &n);
    dfs(1);
    return 0;
}

輸入

3

輸出

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

例題分析

坑爹的奧數

• 題目：
  完成一個奧數題，□□□ + □□□ = □□□，將數字1~9分別填入9個 □ 中，每個數字只能使用一次使得等式成立，例如，173 + 286 = 459就是一個合理的組合，請問一共有多少種合理的組合呢？注意：173+286=459 與 286+173=459是同一種組合！
• 分析：
  這就相當于你手中有編號為1~9的九張牌，然后將這九張牌放到九個盒子中，并使得□□□ + □□□ = □□□成立，其實就是判斷一下 (a[1]+a[4]-a[7])*100+(a[2]+a[5]-a[8])*10+a[3]+a[6]-a[9]==0 這個等式是否成立，

依據上述程式，我們只需修改輸出時的判斷條件即可

#include <stdlib.h>
#include <stdio.h>
int a[100001], n, book[100001], count=0;
void dfs(int step)
{
    int i;
    if(step==n+1 && ((a[1]+a[4]-a[7])*100+(a[2]+a[5]-a[8])*10+a[3]+a[6]-a[9]==0))
    {
        count++;
        return;
    }
    for(i=1; i<=n; i++)
    {
        if(!book[i])
        {
            a[step] = i;
            book[i] = 1;
            dfs(step+1);
            book[i] = 0;
        }
    }
}

int main()
{
    n = 9;
    dfs(1);
    printf("%d", count/2);
    return 0;
}

輸出

168