题目(字符串的排列—牛客网)

输入一个字符串,按字典序打印出该字符串中字符的所有排列(不重复)。例如输入字符串 abc,则打印出由字符 a,b,c 所能排列出来的所有字符串 abc,acb,bac,bca,ca b和 cba。

算法思路

本题为经典的全排列问题，但是要处理一些细节问题。
全排列的思路分为两步：第一步是求所有可能出现在第一个位置上的字符，即把第一个字符和后面所有的字符(包括第一个字符)交换。第二步就是，在固定第一个位置上的字符时，求后面所有字符的全排列，即得到了原问题的子问题，我们利用递归求解即可。
本题中还需要使得输出的字符排列符合字典序，那么我们只要保证在全排列开始前，字符串符合字典序即可，即对字符进行升序即可。另外，这里还可能涉及到排列重复的问题，比如输入字符串 “aa”，那么将会出现重复的排列，解决办法就是在第一个字符和后面的所有字符交换前判断，交换的那对字符是否相同(需排除与自身交换)，若相同可跳过对该元素的交换。

算法实现

拓展：字符串的组合

输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。

算法思路一(递归法)

对于长度为 n 的字符串，我们需要从中选择 m 个字符进行组合，其中 1<=m<=n。我们需要遍历这 m 的可能值，对应于输出含 m 个元素的字符串组合。那么对于每一个组合，如果我们选中了字符串的第一个位置，那么只要递归求解子问题：从长度为 n-1 的字符串中选择 m-1 个字符进行组合，而如果字符串的第一个位置不选，那么只要递归求解子问题：从长度为 n-1 的字符串中选择 m 个字符进行组合。

算法思路二(位操作)

假设字符串长度为 n，那么恰好它的所有组合均可由 1 到 (1<<n)二进制数表示得到，例如 001 对应于组合 a，111对应于组合 abc 等。因此，我们只要把二进制中的 1 对应到所求组合即可。这里我们利用掩码即与操作转换。

算法实现(递归法)

算法实现(位操作)

字符全排列拓展之八皇后问题

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

算法思路

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

算法实现

参考

[1] <<剑指offer2>>
[2] 字符串的全排列和组合算法