前言
字符串的排列組合問題，困擾了我好久，遞歸的思想我今天一定要掌握，擦，話不多說，博客走起！
問題
輸入一個字符串，打印出該字符串中字符的所有排列。例如輸入字符串abc，則輸出由字符a，b，c所能排列出來的所有字符串abc，acb，bac，bca，cab和cba
思路
這是典型的遞歸求解問題，遞歸算法有四個特性：
必須有可達到的終止條件，否則程序陷入死循環
子問題在規模上比原問題小
子問題可通過再次遞歸調用求解
子問題的解應能組合成整個問題的解
對於字符串的排列問題：
如果能生成n-1個元素的全排列，就能生成n個元素的全排列。對於只有一個元素的集合，可以直接生成全排列。所以全排列的遞歸終止條件很明確，只有一個元素時。我們可以分析一下全排列的過程：
首先，我們固定第一個字符a，求後面兩個字符bc的排列
當兩個字符bc排列求好之後，我們把第一個字符a和後面的b交換，得到bac，接著我們固定第一個字符b，求後面兩個字符ac的排列
現在是把c放在第一個位置的時候了，但是記住前面我們已經把原先的第一個字符a和後面的b做了交換，為了保證這次c仍是和原先處在第一個位置的a交換，我們在拿c和第一個字符交換之前，先要把b和a交換回來。在交換b和a之後，再拿c和處於第一位置的a進行交換，得到cba。我們再次固定第一個字符c，求後面兩個字符b、a的排列
既然我們已經知道怎麼求三個字符的排列，那麼固定第一個字符之後求後面兩個字符的排列，就是典型的遞歸思路了
下面這張圖很清楚的給出了遞歸的過程：
示例題目
題目描述
[html] view plaincopyprint?題目描述：
給定一個由不同的小寫字母組成的字符串，輸出這個字符串的所有全排列。
我們假設對於小寫字母有'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
提示：
每組樣例輸出結束後要再輸出一個回車。
題目描述：
給定一個由不同的小寫字母組成的字符串，輸出這個字符串的所有全排列。
我們假設對於小寫字母有'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
提示：
每組樣例輸出結束後要再輸出一個回車。
ac代碼
[cpp] #include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct seq
{
char str[7];
};
struct seq seqs[721];
int count;
void swap(char *str, int a, int b)
{
char temp;
temp = str[a];
str[a] = str[b];
str[b] = temp;
}
void permutation_process(char *name, int begin, int end) {
int k;
if (begin == end - 1) {
strcpy(seqs[count].str, name);
count ++;
}else {
for (k = begin; k < end; k ++) {
swap(name, k, begin);
permutation_process(name, begin + 1, end);
swap(name, k, begin);
}
}
}
int compare(const void *p, const void *q)
{
const char *a = p;
const char *b = q;
return strcmp(a, b);
}
int main()
{
char name[7];
int i, len;
while (scanf("%s", name) != EOF) {
count = 0;
len = strlen(name);
permutation_process(name, 0, len);
qsort(seqs, count, sizeof(seqs[0]), compare);
for (i = 0; i < count; i ++) {
printf("%s\n", seqs[i].str);
}
printf("\n");
}
return 0;
}
/**************************************************************
Problem: 1120
User: wangzhengyi
Language: C
Result: Accepted
Time:710 ms
Memory:920 kb
****************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct seq
{
char str[7];
};
struct seq seqs[721];
int count;
void swap(char *str, int a, int b)
{
char temp;
temp = str[a];
str[a] = str[b];
str[b] = temp;
}
void permutation_process(char *name, int begin, int end) {
int k;
if (begin == end - 1) {
strcpy(seqs[count].str, name);
count ++;
}else {
for (k = begin; k < end; k ++) {
swap(name, k, begin);
permutation_process(name, begin + 1, end);
swap(name, k, begin);
}
}
}
int compare(const void *p, const void *q)
{
const char *a = p;
const char *b = q;
return strcmp(a, b);
}
int main()
{
char name[7];
int i, len;
while (scanf("%s", name) != EOF) {
count = 0;
len = strlen(name);
permutation_process(name, 0, len);
qsort(seqs, count, sizeof(seqs[0]), compare);
for (i = 0; i < count; i ++) {
printf("%s\n", seqs[i].str);
}
printf("\n");
}
return 0;
}
/**************************************************************
Problem: 1120
User: wangzhengyi
Language: C
Result: Accepted
Time:710 ms
Memory:920 kb
****************************************************************/
去掉重復的全排列
上述代碼有個缺陷，就是會造成重復數據的輸出，例如abb這種字符串，上述程序跑完結果如圖：
由於全排列就是從第一個數字起，每個數分別與它後面的數字交換，我們先嘗試加個這樣的判斷——如果一個數與後面的數字相同那麼這兩個數就不交換了。例如abb，第一個數與後面兩個數交換得bab，bba。然後abb中第二個數和第三個數相同，就不用交換了。但是對bab，第二個數和第三個數不同，則需要交換，得到bba。由於這裡的bba和開始第一個數與第三個數交換的結果相同了，因此這個方法不行。
換種思維，對abb，第一個數a與第二個數b交換得到bab，然後考慮第一個數與第三個數交換，此時由於第三個數等於第二個數，所以第一個數就不再用與第三個數交換了。再考慮bab，它的第二個數與第三個數交換可以解決bba。此時全排列生成完畢！
這樣，我們得到在全排列中去掉重復的規則：
去重的全排列就是從第一個數字起，每個數分別與它後面非重復出現的數字交換。
貼出上面ac代碼的去重版本：
[cpp] #include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct seq
{
char str[7];
};
struct seq seqs[721];
int count;
int is_swap(char *str, int begin, int k)
{
int i, flag;
for (i = begin, flag = 1; i < k; i ++) {
if (str[i] == str[k]) {
flag = 0;
break;
}
}
return flag;
}
void swap(char *str, int a, int b)
{
char temp;
temp = str[a];
str[a] = str[b];
str[b] = temp;
}
void permutation_process(char *name, int begin, int end) {
int k;
if (begin == end - 1) {
strcpy(seqs[count].str, name);
count ++;
}else {
for (k = begin; k < end; k ++) {
if (is_swap(name, begin, k)) {
swap(name, k, begin);
permutation_process(name, begin + 1, end);
swap(name, k, begin);
}
}
}
}
int compare(const void *p, const void *q)
{
const char *a = p;
const char *b = q;
return strcmp(a, b);
}
int main()
{
char name[7];
int i, len;
while (scanf("%s", name) != EOF) {
count = 0;
len = strlen(name);
permutation_process(name, 0, len);
qsort(seqs, count, sizeof(seqs[0]), compare);
for (i = 0; i < count; i ++) {
printf("%s\n", seqs[i].str);
}
printf("\n");
}
return 0;
}
