Question

c++|全排列算法

Answer 1

比如数组[1,2,3]，一直固定第一位，对剩下的元素进行全排列（把不同的元素依次放到第一位。）
(1) 首先固定1，即1放到第一位，对后两个元素进行全排列；
(2) 固定2，即更换1与2的位置，数组变成[2,1,3]，固定2，对[1,3]进行全排列；
(3) 交换1与3的位置，固定3，对[2,1]进行全排列。
本质上是一个 递归 问题。
需要注意的是 ，每一次更换完，全排列完以后，要将数组恢复，即再用一次 swap 函数，否则会有重复的交换，输出重复的排列情况。

①在main函数中拿到原序列以后，首先用 sort 函数将它字典序排列，比如从badcfe变成abcdef
②swap函数更改一下，比如一开始是序列为abcdef，交换a和d，我们不是简单的变成dbcaef，而是变成dabcef，这样可以保证下次递归时使用的是“abcef”这个按照字典序排列的子序列（数组的简单移动即可实现），这样除了第一位，后面的仍然是按照字典序。可以理解为把j位置的字符插入到i字符前面，i-j之间的的字符串都后移一位。e.g. swap("abcdef", 2, 5): abcdef -> abfcde
③swap函数的回溯也要重写一个swapback，让序列恢复到swap之前的状态

完整按照字典序的全排列算法如下：(这里将数组改成了字符数组)
需要注意的是排序函数的参数也必须是排好序的数组，即先用 sort 函数处理输入。

例题
也可以用上述 swap 的来解决，这里给出另一种方法。