使用C語言解決字符串全排列問題
問題
輸入一個(gè)字符串，打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc，則輸出由字符a，b，c所能排列出來的所有字符串a(chǎn)bc，acb，bac，bca，cab和cba
思路
這是典型的遞歸求解問題，遞歸算法有四個(gè)特性：
- 必須有可達(dá)到的終止條件，否則程序陷入死循環(huán)
- 子問題在規(guī)模上比原問題小
- 子問題可通過再次遞歸調(diào)用求解
- 子問題的解應(yīng)能組合成整個(gè)問題的解
對(duì)于字符串的排列問題：
如果能生成n-1個(gè)元素的全排列，就能生成n個(gè)元素的全排列。對(duì)于只有一個(gè)元素的集合，可以直接生成全排列。所以全排列的遞歸終止條件很明確，只有一個(gè)元素時(shí)。我們可以分析一下全排列的過程：
- 首先，我們固定第一個(gè)字符a，求后面兩個(gè)字符bc的排列
- 當(dāng)兩個(gè)字符bc排列求好之后，我們把第一個(gè)字符a和后面的b交換，得到bac，接著我們固定第一個(gè)字符b，求后面兩個(gè)字符ac的排列
- 現(xiàn)在是把c放在第一個(gè)位置的時(shí)候了，但是記住前面我們已經(jīng)把原先的第一個(gè)字符a和后面的b做了交換，為了保證這次c仍是和原先處在第一個(gè)位置的a交換，我們?cè)谀胏和第一個(gè)字符交換之前，先要把b和a交換回來。在交換b和a之后，再拿c和處于第一位置的a進(jìn)行交換，得到cba。我們?cè)俅喂潭ǖ谝粋€(gè)字符c，求后面兩個(gè)字符b、a的排列
- 既然我們已經(jīng)知道怎么求三個(gè)字符的排列，那么固定第一個(gè)字符之后求后面兩個(gè)字符的排列，就是典型的遞歸思路了
下面這張圖很清楚的給出了遞歸的過程：
基本解決方法
方法1：依次從字符串中取出一個(gè)字符作為最終排列的第一個(gè)字符，對(duì)剩余字符組成的字符串生成全排列，最終結(jié)果為取出的字符和剩余子串全排列的組合。
#include <iostream>
#include <string>
using namespace std;
void permute1(string prefix, string str)
{
if(str.length() == 0)
cout << prefix << endl;
else
{
for(int i = 0; i < str.length(); i++)
permute1(prefix+str[i], str.substr(0,i)+str.substr(i+1,str.length()));
}
}
void permute1(string s)
{
permute1("",s);
}
int main()
{
//method1, unable to remove duplicate permutations.
cout << "method1" << endl;
permute1("ABA");
}
優(yōu)點(diǎn)：該方法易于理解，但無法移除重復(fù)的排列，如：s="ABA"，會(huì)生成兩個(gè)“AAB”。
方法2：利用交換的思想，具體見實(shí)例，但該方法不如方法1容易理解。
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
void swap(char* x, char* y)
{
char tmp;
tmp = *x;
*x = *y;
*y = tmp;
}
/* Function to print permutations of string
This function takes three parameters:
1. String
2. Starting index of the string
3. Ending index of the string. */
void permute(char *a, int i, int n)
{
int j;
if (i == n)
printf("%s\n", a);
else
{
for (j = i; j <= n; j++)
{
if(a[i] == a[j] && j != i) //為避免生成重復(fù)排列，當(dāng)不同位置的字符相同時(shí)不再交換
continue;
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j)); //backtrack
}
}
}
int main()
{
//method2
cout << "method2" << endl;
char a[] = "ABA";
permute(a,0,2);
return 0;
}
兩種方法的生成結(jié)果：
method1 ABA AAB BAA BAA AAB ABA method2 ABA AAB BAA
下面來看ACM題目實(shí)例
示例題目
題目描述
題目描述：
給定一個(gè)由不同的小寫字母組成的字符串，輸出這個(gè)字符串的所有全排列。
我們假設(shè)對(duì)于小寫字母有'a' < 'b' < ... < 'y' < 'z'，而且給定的字符串中的字母已經(jīng)按照從小到大的順序排列。
輸入：
輸入只有一行，是一個(gè)由不同的小寫字母組成的字符串，已知字符串的長(zhǎng)度在1到6之間。
輸出：
輸出這個(gè)字符串的所有排列方式，每行一個(gè)排列。要求字母序比較小的排列在前面。字母序如下定義：
已知S = s1s2...sk , T = t1t2...tk，則S < T 等價(jià)于，存在p (1 <= p <= k)，使得
s1 = t1, s2 = t2, ..., sp - 1 = tp - 1, sp < tp成立。
樣例輸入：
abc
樣例輸出：
abc
acb
bac
bca
cab
cba
提示：
每組樣例輸出結(jié)束后要再輸出一個(gè)回車。
ac代碼
#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
****************************************************************/
去掉重復(fù)的全排列
上述代碼有個(gè)缺陷，就是會(huì)造成重復(fù)數(shù)據(jù)的輸出，例如abb這種字符串，上述程序跑完結(jié)果如圖：
由于全排列就是從第一個(gè)數(shù)字起，每個(gè)數(shù)分別與它后面的數(shù)字交換，我們先嘗試加個(gè)這樣的判斷——如果一個(gè)數(shù)與后面的數(shù)字相同那么這兩個(gè)數(shù)就不交換了。例如abb，第一個(gè)數(shù)與后面兩個(gè)數(shù)交換得bab，bba。然后abb中第二個(gè)數(shù)和第三個(gè)數(shù)相同，就不用交換了。但是對(duì)bab，第二個(gè)數(shù)和第三個(gè)數(shù)不同，則需要交換，得到bba。由于這里的bba和開始第一個(gè)數(shù)與第三個(gè)數(shù)交換的結(jié)果相同了，因此這個(gè)方法不行。
換種思維，對(duì)abb，第一個(gè)數(shù)a與第二個(gè)數(shù)b交換得到bab，然后考慮第一個(gè)數(shù)與第三個(gè)數(shù)交換，此時(shí)由于第三個(gè)數(shù)等于第二個(gè)數(shù)，所以第一個(gè)數(shù)就不再用與第三個(gè)數(shù)交換了。再考慮bab，它的第二個(gè)數(shù)與第三個(gè)數(shù)交換可以解決bba。此時(shí)全排列生成完畢！
這樣，我們得到在全排列中去掉重復(fù)的規(guī)則：
去重的全排列就是從第一個(gè)數(shù)字起，每個(gè)數(shù)分別與它后面非重復(fù)出現(xiàn)的數(shù)字交換。
貼出上面ac代碼的去重版本：
#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;
}
相關(guān)文章
這篇文章主要介紹了C++11顯示類型轉(zhuǎn)換的優(yōu)點(diǎn)，幫助大家更好的理解和學(xué)習(xí)c++，感興趣的朋友可以了解下，希望能給你帶來幫助2021-08-08
C++ 實(shí)現(xiàn)帶監(jiān)視哨的順序查找算法
這篇文章主要介紹了C++ 實(shí)現(xiàn)帶監(jiān)視哨的順序查找算法，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-03-03
C語言實(shí)現(xiàn)簡(jiǎn)單三子棋小游戲
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡(jiǎn)單三子棋小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-06-06
使用map實(shí)現(xiàn)單詞轉(zhuǎn)換的實(shí)例分析
本篇文章是對(duì)使用map實(shí)現(xiàn)單詞轉(zhuǎn)換的代碼實(shí)例進(jìn)行了纖細(xì)的分析介紹，需要的朋友參考下2013-05-05
C/C++實(shí)現(xiàn)圖形學(xué)掃描線填充算法
這篇文章主要介紹了C/C++實(shí)現(xiàn)圖形學(xué)掃描線填充算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-04-04
C語言數(shù)組應(yīng)用實(shí)現(xiàn)三子棋游戲
這篇文章主要為大家詳細(xì)介紹了C語言數(shù)組應(yīng)用實(shí)現(xiàn)三子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章說明了什么是結(jié)構(gòu)體,介紹了結(jié)構(gòu)體的概念和使用優(yōu)點(diǎn),在C語言中如何使用和初始化結(jié)構(gòu)體方法,通過詳細(xì)的代碼展開進(jìn)行說明,希望該篇文章對(duì)你有所幫助2021-06-06
C語言中的常量分為以下幾種：字面常量、const修飾的常變量、#define定義的標(biāo)識(shí)符常量等，下面我們將詳細(xì)對(duì)C語言這幾個(gè)常量做介紹，感興趣的小伙伴可以參考一下2021-09-09
c/c++獲取系統(tǒng)時(shí)間函數(shù)的方法示例
這篇文章主要介紹了c/c++獲取系統(tǒng)時(shí)間函數(shù)的方法示例，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02
C++核心編程之占位參數(shù)和默認(rèn)參數(shù)
這篇文章主要介紹了C++核心編程之占位參數(shù)和默認(rèn)參數(shù)，c++中函數(shù)的形參列表中的形參是可以有默認(rèn)值的，函數(shù)的形參列表里可以有占位參數(shù)，用來占位，調(diào)用函數(shù)時(shí)必須填補(bǔ)位置。下面更多相關(guān)內(nèi)容的詳細(xì)介紹，需要的小伙伴可以參考一下2022-03-03