Open Judge2748:全排列

今天在學習北京大學的MOOC程式設計與算法分析，學到了遞歸的章節，裡面有這麼一道作業題。是這樣說的：

描述

給定一個由不同的小寫字母組成的字元串，輸出這個字元串的所有全排列。 我們假設對于小寫字母有’a’ < ‘b’ < … < ‘y’ < ‘z’，而且給定的字元串中的字母已經按照從小到大的順序排列。

輸入

輸入隻有一行，是一個由不同的小寫字母組成的字元串，已知字元串的長度在1到6之間。

輸出

輸出這個字元串的所有排列方式，每行一個排列。要求字母序比較小的排列在前面。字母序如下定義：

已知S = s1s2…sk , T = t1t2…tk，則S < T 等價于，存在p (1 <= p <= k)，使得

s1 = t1, s2 = t2, …, sp - 1 = tp - 1, sp < tp成立。

樣例輸入

abc

樣例輸出

abc

acb

bac

bca

cab

cba

首先先給出代碼。雖然剛聽老師講了N皇後問題，感覺裡面的遞歸思想和本題類似。但是我一下子還是沒有寫出來，參考了其他人的代碼後寫出了此段代碼，感謝大神。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>  //在後面使用memset函數和strlen需要包含這個頭檔案
using namespace std;

const int N=; 
char str[N];
char result[N];
int isVisit[N];
int num = ;

void PutStr(int n){
    if(n == num){
        cout << result << endl;
        return ;
    }
    for(int i = ; i < num; i++){
        if(isVisit[i] == ){
            isVisit[i] = ;
            result[n] = str[i];
            PutStr(n + );  //開始遞歸
            isVisit[i] = ;
        }
    }
}

int main(){
    memset(result,,sizeof(result));  //初始化操作
    memset(isVisit,,sizeof(isVisit));
    while(cin >> str){
        num = strlen(str);
        PutStr();
        cout << endl;
    }
    return ;
}
           

以後我的文章都會使用Markdown來寫，這裡面代碼的格式有一些不一樣。

這裡解釋一下PutStr函數。PutStr裡面的遞歸還是比較巧妙的。首先進來會判斷n和num是否相等，如果相等了就把結果輸出來，作為一種排列方式。

再來說後面的一個循環。這個循環從i=0開始，isVisit[N]是用來存儲字元是不是已經用過了。如果isVisit[i]==0，說明沒被用過，就進入if，同時标記為1.接下來把此字元放入result[n]裡面。注意，n一開始是0，接下來開始遞歸PutStr（n+1）。PutStr（n+1）裡面的循環仍是從i=0開始的，直到找到未被使用的字元，繼續遞歸。這樣直到最後，一種方案就形成了。之後開始傳回。以abc的例子為例，第一次形成abc後，會再形成acb。