Q：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
T：
（部分内容引自：https://www.cnblogs.com/cxjchen/p/3932949.html）
我们先来看一个计算题：
字符串“alibaba”有_____个不同的排列。
A. 5040 B. 840 C. 14 D.420
计算方法：(A_7^7/(A_2^2*A_3^3)=420)
A.
递归算法：
对于字符串的排列问题：如果能生成n-1个元素的全排列，就能生成n个元素的全排列。对于只有一个元素的集合，可以直接生成全排列。所以全排列的递归终止条件很明确，只有一个元素时。我们可以分析一下全排列的过程：
1.首先，我们固定第一个字符a，求后面两个字符bc的排列
2.当两个字符bc排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列
3.现在是把c放在第一个位置的时候了，但是记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍是和原先处在第一个位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处于第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列
4.既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排列，就是典型的递归思路了
还有一个问题要注意，就是如果字符串中有重复的字符串.由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换 了。例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。
换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！
这样，我们得到在全排列中去掉重复的规则：
去重的全排列就是从第一个数字起，每个数分别与它后面非重复出现的数字交换。
代码：
private:
vector<string> result;
public:
vector<string> Permutation(string str) {
if(str.empty())
return result;
sort(str.begin(), str.end());
Permutations(str, 0);
return result;
}
void Permutations(string str, int index) {
int size = str.size();
if (index == size) {
//递归到最后，可以把结果放入了
result.push_back(str);
return;
}
for (int i = index; i < size; i++) {
if (str[i] == str[i + 1])
//如果相同后面字母和前面相同，就不需要交换了，解决重复的问题
continue;
//交换子串的第一个字符和后续字符
swap(str[i], str[index]);
//子串递归
Permutations(str, index + 1);
}
}
或者用回溯法做
1.没有重复的
private List<List<Integer>> result;
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums.length == 0)
return result;
result = new LinkedList<>();
List<Integer> list = new LinkedList<>();
permute(nums, list);
return result;
}
private void permute(int[] nums, List<Integer> list) {
if (list.size() == nums.length) {
List<Integer> list1 = new LinkedList<>(list);
result.add(list1);
return;
}
for (int num : nums) {
if (list.contains(num))
continue;
list.add(num);
permute(nums, list);
list.remove(list.size() - 1);
}
}
2.有重复
private List<List<Integer>> result;
private boolean[] need;//判断一下是否读取过
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums.length == 0)
return result;
result = new LinkedList<>();
need = new boolean[nums.length];
Arrays.fill(need, false);
List<Integer> list = new LinkedList<>();
Arrays.sort(nums);//一定记得要sort，不然后面相等略去就过不去
permute(nums, list);
return result;
}
private void permute(int[] nums, List<Integer> list) {
if (list.size() == nums.length) {
List<Integer> list1 = new LinkedList<>(list);
result.add(list1);
return;
}
for (int i = 0; i < nums.length; i++) {
if (need[i])
continue;
list.add(nums[i]);
need[i] = true;
permute(nums, list);
list.remove(list.size() - 1);
need[i] = false;
while (i + 1 < nums.length && nums[i] == nums[i + 1])//有相等的跳过去
i++;
}
}
字典排序算法：（非递归算法，引用：https://blog.csdn.net/happyrocking/article/details/83619392）
字典序算法用来解决这样一个问题：给定其中一种排列，求基于字典序的下一种排列。
比如给定一种排列为 abc，则其基于字典序的下一种排列为 acb。
要求下一种排列既要比原排列大，又不能有第三种排列位于他俩之间。即下一种排列为大于原排列的最小排列。
以输入为 358764 为例，字典序算法的步骤：
1、从原排列中，从右至左，找到第一个左邻小于右邻的字符，记左邻位置为 a。
示例中 a=1，list[a] = 5。
2、重新从右至左，找到第一个比 list[a] 大的字符，记为位置为 b。
示例中 b=4，list[b] = 6。
3、交换 a 和 b 两个位置的值。
示例变为了 368754。
4、将 a 后面的数，由小到大排列。
示例变为了 364578。
算法结束，输出 364578。
用于全排列时，如图：
代码：
private:
vector<string> result;
public:
vector<string> Permutation(string str) {
if (str.empty())
return result;
sort(str.begin(), str.end());
int size = str.size();
int left = size - 1;
int right = size - 1;
bool flag = false;
while (true) {
result.push_back(str);
for (int i = size - 1; i >= 0; i--) {
if (str[i] < str[i + 1]) {
flag = true;
left = i;
break;
}
}
if (!flag)
break;
flag = false;
for (int i = size - 1; i >= 0; i--) {
if (str[i] > str[left]) {
right = i;
break;
}
}
swap(str[left], str[right]);
sort(str.begin() + left + 1, str.end());
left = right = size - 1;
}
return result;
}
当然，实际上……C++的STL库中直接有全排序的函数，前提是数据必须有序。next_permutation(temp.begin(), temp.end())求的是当前排列的下一个排列，所以用do_while防止缺失默认第一种情况。
private:
vector<string> result;
public:
vector<string> Permutation(string str) {
if(str.empty())
return result;
sort(str.begin(), str.end());
//注意这里要用do_while，否则会缺失默认输入
do {
result.push_back(str);
} while (next_permutation(str.begin(), str.end()));
return result;
}