Question

题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

如何求出几个字符的所有排列，很多人都不能一下子想出解决方案。那我们是不是可以考虑把这个复杂的问题分解成小的问题呢？比如，我们把一个字符串看成由两部分组成：第一部分为它的第一个字符，第二部分是后面的所有字符。在图4.14中，我们用两种不同的背景颜色区分字符串的两部分。

我们求整个字符串的排列，可以看成两步：首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。图4.14就是分别把第一个字符a和后面的b、c等字符交换的情形。首先固定第一个字符（如图4.14（a）所示），求后面所有字符的排列。这个时候我们仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换（如图4.14（b）所示）……

图4.14　求字符串的排列的过程

注：（a）把字符串分为两部分，一部分是字符串的第一个字符，另一部分是第一个字符以后的所有字符（有阴影背景的区域）。接下来我们求阴影部分的字符串的排列。（b）拿第一个字符和它后面的字符逐个交换。

分析到这里，我们就可以看出，这其实是很典型的递归思路，于是我们不难写出如下代码：

在函数Permutation（char^* pStr, char^* pBegin）中，指针pStr指向整个字符串的第一个字符，pBegin指向当前我们做排列操作的字符串的第一个字符。在每一次递归的时候，我们从pBegin向后扫描每一个字符（即指针pCh指向的字符）。在交换pBegin和pCh指向的字符之后，我们再对pBegin后面的字符串递归地做排列操作，直至pBegin指向字符串的末尾。

源代码：

本题完整的源代码详见28_StringPermutation项目。

测试用例：

- 功能测试（输入的字符串中有1个或者多个字符）。

- 特殊输入测试（输入的字符串的内容为空或者是NULL指针）。

本题考点：

- 考查思维能力。当整个问题看起来不能直接解决的时候，应聘者能否想到把字符串分成两部分，从而把大问题分解成小问题来解决，是能否顺利解决这个问题的关键。

- 考查对递归的理解和编程能力。

本题扩展：

如果不是求字符的所有排列，而是求字符的所有组合，应该怎么办呢？还是输入三个字符a、b、c，则它们的组合有a、b、c、ab、ac、bc、abc。当交换字符串中的两个字符时，虽然能得到两个不同的排列，但却是同一个组合。比如ab和ba是不同的排列，但只算一个组合。

如果输入n个字符，则这n个字符能构成长度为1的组合、长度为2的组合、……、长度为n的组合。在求n个字符的长度为m（1≤m≤n）的组合的时候，我们把这n个字符分成两部分：第一个字符和其余的所有字符。如果组合里包含第一个字符，则下一步在剩余的字符里选取m－1个字符；如果组合里不包含第一个字符，则下一步在剩余的n－1个字符里选取m个字符。也就是说，我们可以把求n个字符组成长度为m的组合的问题分解成两个子问题，分别求n－1个字符串中长度为m－1的组合，以及求n－1个字符的长度为m的组合。这两个子问题都可以用递归的方式解决。

相关题目：

1．输入一个含有8个数字的数组，判断有没有可能把这8个数字分别放到正方体的8个顶点上（如图4.15所示），使得正方体上三组相对的面上的4个顶点的和都相等。

图4.15　把8个数字放到正方体的8个顶点上

这相当于先得到a1、a2、a3、a4、a5、a6、a7和a8这8个数字的所有排列，然后判断有没有某一个的排列符合题目给定的条件，即a1＋a2＋a3＋a4＝a5＋a6＋a7＋a8，a1＋a3＋a5＋a7＝a2＋a4＋a6＋a8，并且a1＋a2＋a5＋a6＝a3＋a4＋a7＋a8。

2．在8×8的国际象棋上摆放8个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行、同一列或者同一对角线上。图4.16中的每个黑色格子表示一个皇后，这就是一种符合条件的摆放方法。请问总共有多少种符合条件的摆法？

图4.16　8×8的国际象棋棋盘上摆着8个皇后（黑色小方格），任意两个皇后不在同一行、同一列或者同一对角线上

由于8个皇后的任意两个不能处在同一行，那么肯定是每一个皇后占据一行。于是我们可以定义一个数组ColumnIndex[8]，数组中第i个数字表示位于第i行的皇后的列号。先把数组ColumnIndex的8个数字分别用0～7初始化，接下来就是对数组ColumnIndex做全排列。因为我们是用不同的数字初始化数组，所以任意两个皇后肯定不同列。我们只需判断每一个排列对应的8个皇后是不是在同一对角线上，也就是对于数组的两个下标i和j，是不是i-j=ColumnIndex[i]-ColumnIndex[j]或者j-i=ColumnIndex[i]-ColumnIndex[j]。

举一反三：

如果面试题是按照一定要求摆放若干个数字，我们可以先求出这些数字的所有排列，然后再一一判断每个排列是不是满足题目给定的要求。