字符串的全排列（字典序排列）
题⽬描述
输⼊⼀个字符串，打印出该字符串中字符的所有排列。例如输⼊字符串abc，则输出由字符a、b、c 所能排列出来的所有字符串abc, acb, bac, bca, cab, cba。字符串长度排序c语言
题⽬分析
穷举与递归
⼜是⼀个经典问题，最容易想到的解决⽅法仍然是穷举（我实在是太爱穷举法了，每当被问到算法问题不知道如何解决的时候，总可以祭出穷举⼤旗，从⽽多争取3分钟的思考时间
）。穷举虽好，但它⼤多数情况下都不是被需要的那个答案，是因为看起来代码太Low不够⾼⼤上吗？
在这种情况下，穷举法裹着貂⽪⼤⾐的亲戚——递归就出现了。虽然空间复杂度和时间复杂度没有任何改进，⽽且还增加了系统开销（关于递归法的系统开销不在这⾥讨论，之后再专门的时间阐述），但是就是因为长得好看（代码看起来精炼），递归的B格⼉就⾼了很多。
递归法对于这个题⽬同样⾮常适⽤，基本思路就是固定⼀个字符，然后对剩余的字符做全排列……不赘述，请⾃⼰想。如果你也跟我⼀样永远想不明⽩递归，那就画画图，写写代
码，debug⼀下，每天花3-4个⼩时，静下⼼来仔细捉摸，总（ye）会（bu）想（hui）明⽩的。贴⼀段July和他伙伴们在《程序员编程艺术：⾯试和算法⼼得》中的代码实现，供做噩梦时使⽤。p.s. 我已加了注释
/*
* Permute full array of input string by general recusion
* @ char* perm [in/out] The string need to do permutation
* @ int from [in] The start position of the string
* @ int to [in] The end position of the string
*/
void CalcAllPermutation(char* perm, int from, int to)
{
if (to <= 1)
{
return;
}
if (from == to)
{
//all characters has been permuted
for (int i = 0; i <= to; i++)
cout << perm[i];
cout << endl;
}
else
{
// always select one character, then full array the left ones.
for (int j = from; j <= to; j++)
{
swap(perm[j], perm[from]); //swap the selected character to the beginning of string
CalcAllPermutation(perm, from + 1, to); // Permute left characters in full array.
swap(perm[j], perm[from]); //recovery the string to original one (swap the selected character back to its position.)
}
}
}
字典序
这是⼀个⽐递归更有趣的答案，不知道算不算经典解法，起码开拓了思路，跟每⼀次接触新鲜的算法⼀样，仍然想了半天的时间，因此照例把思考过程更细致的记录下来（虽然July和他伙伴们在《程序员编程艺术：⾯试和算法⼼得》中已经说了很多），再加上⼀些⼩修改。
字典序，顾名思义，就是按照字典的顺序进⾏排列。根据的定义：给定两个偏序集A和B,(a,b)和(a′,b′)属于笛卡尔集 A × B，则字典序定义为(a,b) ≤ (a′,b′) 当且仅当 a < a′或 (a = a′且 b ≤ b′)。所以给定两个字符串，逐个字符⽐较，那么先出现较⼩字符的那个串字典顺序⼩，如果字符⼀直相等，较短的串字典顺序⼩。例如：abc < abcd < abde < afab。
总结⼀下，字典序排序其实就是同⼀组字符组成的⼀系列字符串，
起点：字典序最⼩的排列, 1~n , 例如12345
终点：字典序最⼤的排列，n~1, 例如54321
过程：从当前字符串排列⽣成字典序刚好⽐它⼤的下⼀个排列，⽐如12345的字典序下⼀个排列是12354
现在来进⼀步分析⼀下算法实现，其实对于字典序排列，关键点就是到“下⼀个排列”。基本的查⽅法
假定现有字符串(A)x(B)，它的下⼀个排列是：(A)y(B’)，其中A、B和B’是“字符串”(可能为空），x和y是“字符”，前缀相同，都是A，且⼀定有y > x。那么，为使下⼀个排列字典顺序尽可能⼩，必有：
A尽可能长（A越长，那么B‘就越短，从⽽y所在的位越低，很明显的同⼀个字符放在低位肯定⽐放在⾼位要⼩，⽐如：100<10< 1, abc<aac<aaa）
y尽可能⼩（同⼀个位置上，字符越⼩整个字符串的字典序越⼩，⽐如：131<121, a c d<a b c）
B'⾥的字符按由⼩到⼤递增排列 (⼩朋友都懂的道理不解释)
现在的问题是如何到“x”和“y”?
举个例⼦，现在我们要21543的下⼀个排列，我们可以从左⾄右逐个扫描每个数，看哪个能增⼤（⾄于如何判定能增⼤，是根据如果⼀个数右⾯有⽐它⼤的数存在，那么这个数就能增⼤），我们可以看到最后⼀个能增⼤的数是：x = 1。⽽1应该增⼤到多少？1能增⼤到它右⾯⽐它⼤的那⼀系列数中最⼩的那个数，即：y = 3，故此时21543的下⼀个排列应该变为
23xxx，显然 xxx(对应之前的B’）应由⼩到⼤排，于是我们最终到⽐“21543”⼤，但字典顺序尽量⼩的23145，到的23145刚好⽐21543⼤。
抽象概括⼀下上⾯的例⼦就是“⼆、⼀交换、⼀翻转”。
1. ⼀：到排列中最后（最右）⼀个升序的⾸位位置i，x = ai
2. ⼆：到排列中第i位右边最后⼀个⽐ai ⼤的位置j，y = aj
3. ⼀交换：交换x，y
4. ⼀翻转：把第(i+ 1)位到最后的部分翻转
*升序：相邻两个位置ai < ai+1，ai 称作该升序的⾸位
21543的下⼀个排列，套⽤“⼆、⼀交换、⼀翻转”就是
1. ⼀: 到排列中最后（最右）⼀个升序的⾸位, x = 1
2. ⼆: 到排列中1的右边最后⼀个⽐1⼤的位置，y = 3
3. ⼀交换：1和3交换，得23541
4. ⼀翻转：翻转541，得23145
道理讲完了，但是你真的懂了吗？反正本⼈看到这⾥⼜看了算法之后，仍然懵懵懂懂（请原谅我的智商吧，其实我⾃⼰也挺着急的，妈妈已经急哭，表⽰对我放弃了）。因此，下⾯的部分很重要。
⾸先来看第⼀“到排列中最后（最右）⼀个升序的⾸位位置i，x = ai”
这意味着什么？这意味着字符串在x之后所有字符都是降序排列的，如下图。在到x=1之前，543已经达到了最⼤字典序，因此不可能通过改变543的顺序得到更⼤的字符串。
那么为什么不是修改⾸位的“2”呢？还记得前⾯介绍的字符串(A)x(B)的下⼀个排列是(A)y(B’)的⽅法吗？，A要尽可能长。对“1”进⾏操作正式保证了A尽可能长。
接下来，看⼀下第⼆和⼀交换：“到排列中第i位右边最后⼀个⽐ai ⼤的位置j，y = aj”，“交换x，y”
说完了“A要尽可能长”，现在该说y要尽可能⼩了。为什么“第⼆”和“⼀交换”之后，y就最⼩了呢？既然⾸位的“2”是不在范围内的，⽽“1”（即x）是要被交换的，那么y只能来
⾃“5”，“4”，'3“，因为543是降序排列的（注意，x可是到的字符串中最后⼀个升序的⾸位哟），因此“5”，“4”，'3“中⽐”1“（即x）⼤的最⼩的字符就是y。于是y=3。交换x，y之后，即得到新的字符串(A)y(B')
此时的B'仍然不是我们最终需要的B'，因为它还不满⾜最后⼀个条件B'⾥的字符按由⼩到⼤递增排列。
为了做到这⼀点，于是有了最后的“⼀翻转”。那么为什么简单的翻转之后B'⾥的字符就按照由⼩到⼤的顺序排列了呢？
我们在来回顾⼀下B和B‘的确定过程。⾸先，B是⼀个降序排列的字符串；然后我们在B中到了⽐x⼩的最⼩的y（此处有些绕，⾃⼰写⼏个字符串就⼀⽬了然了），也就是说y的右侧如果还有字符的话也⼀定⽐x⼩（因为B是降序），接下来交换x和y得到B'，因此B’也是降序的。
对于⼀个降序的字符串来说，翻转之后即为升序排列。于是我们得到了最终的(A)y(B')，即23145。
代码实现
好了，该讲的都讲完了，现在看代码
/*
* Find out the next (bigger) permutation of current string.
* @ char* perm [in/out] String
* @ int num [in] The length of string.
*/
bool FindNextPermutation(char* perm, int num)
{
int i = 0;
for(i = num - 2; (perm[i] >= perm[i+1]) && i >= 0; --i)
; // Find x
if(i < 0)
{
return false;  // The input string is a single character
}
int j = 0;
for(j = num - 1; (j > i) && perm[j] <= perm[i]; --j)
; // Find y
swap(perm[i], perm[j]);  // swap x and y
reverse(perm + i + 1, perm + num); // reverse B'
return true;
}
这段代码实现了从当前字符串⽣成字典序刚好⽐它⼤的下⼀个排列，但是如果我们拿到的字符串不是字典序最⼩的排列，该如何处理呢？
对原始字符串进⾏排序，将原始字符串转换为字典序最⼩的排列后，再通过字典序排序进⾏全排列。这样做的好处是实现简单，缺点是要多做⼀次字符串排序。关于排序算法不在本⽂讨论范围，这⾥我直接使⽤了STL的sort函数
void CalcByDictionary(const string &str)
{
char* perm = const_cast<char*>(str.c_str());
sort(perm, perm+str.size());
cout<<str<<endl;
while(true)
{
if(!FindNextPermutation(perm, str.size()))
{
break;
}
cout<<s<<endl;
}
}
题外话
最近⼀直在看July和他伙伴们的《程序员编程艺术：⾯试和算法⼼得》，收获良多。在学习的过程中发现，虽然原书讲解的很细致，但是真正理解仍然需要花费⼤量的思考和实践。因此做了这个系列的⽂章，只是希望将⾃⼰的思考记录下来，供以后查阅。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。