前言
猛起更新。
正文
问题来源
既然被问到了全排列，索性来个全家桶。
问题描述
给你一个数组，给出字典序全排列。
示例 1:
输入： [1,2,3,4]
输出：
1234, 1243, 1324, 1342, 1423, 1432,
2134, 2143, 2314, 2341, 2413, 2431,
3124, 3142, 3214, 3241, 3412, 3421,
4123, 4132, 4213, 4231, 4312, 4321.
分析：
非递归求解过程
分析这种过程，看后一个排列与前一个排列之间有什么关系？
再如，设有排列(p)=2763541，按照字典式排序，它的下一个排列是什么？
2763541 （找最后一个正序35） 2763541 （找3后面比3大的最后一个数4） 2764531 （交换3,4的位置） 2764135 （把4后面的5,3,1反转） 下面给出求 p[1…n] 的下一个排列的描述：
求 i = max{j | p[j – 1] < p[j]} （找最后一个正序） 求 j = max{k| p[i – 1] < p[k]} （找最后大于 p[i – 1] 的） 交换 p[i – 1] 与 p[j]得到 p[1] … p[i-2] p[j] p[i] p[i+1] … p[j-1] p[i-1] p[j+1] … p[n] 反转 p[j] 后面的数得到 p[1] … p[i-2] p[j] p[n] … p[j+1] p[i-1] p[j-1] … p[i]
private static void PermutationList()
{
int fromIndex, endIndex, changeIndex;
Sort(0, length - 1);
do
{
// 输出一种全排列
Output();
fromIndex = endIndex = length - 1;
// 向前查找第一个变小的元素
while (fromIndex > 0 && words[fromIndex] < words[fromIndex - 1]) --fromIndex;
changeIndex = fromIndex;
if (fromIndex == 0) break;
// 向后查找最后一个大于words[fromIndex-1]的元素
while (changeIndex + 1 < length && words[changeIndex + 1] > words[fromIndex - 1]) ++changeIndex;
Swap(fromIndex - 1, changeIndex); // 交换两个值
InvertArray(fromIndex, endIndex); // 对后面的所有值进行反向处理
} while (true);
}
递归求解过程
private static void PermutationList(int fromIndex, int endIndex)
{
if (fromIndex == endIndex)
Output();
else
{
for (int index = fromIndex; index <= endIndex; ++index)
{
// 此处排序主要是为了生成字典序全排列，否则递归会打乱字典序
Sort(fromIndex, endIndex);
Swap(fromIndex, index);
PermutationList(fromIndex + 1, endIndex);
Swap(fromIndex, index);
}
}
}
参考文档
【LeetCode】 Permutations 排列生成算法之字典序法
字典序全排列算法研究
总结：
勤思考。
结语
不管怎么样好好加油。
