求下一排列问题和全排列问题
排列，字典序与下一排列假设你有一个数组或序列，下一个排列是指在字典序上比当前排列更大的排列。如果当前排列已经是最大的排列，那么下一个排列是最小的排列。
例如，给定一个数组 ，它的下一个排列是 ；再下一个是；而对于 ，它已经是最大排列；一般规定下一个排列又循环到最小排列，即 。
求下一排列的关键是从当前排列出发，利用字典序的性质来找到下一个更大的排列。这个算法的核心步骤如下：
[*]从右向左扫描数组，找到第一个下降的位置。即找到一个元素 nums，使得 nums < nums。这个位置的存在意味着当前排列还可以变大。如果没有找到这样的 i，说明当前排列已经是最大的排列。
[*]找到比 nums 大的最小元素：找到 i 以右比他大的最小元素（由于 i 以后都是递减的，即最后一个）。
[*]交换元素：交换 nums 和 nums，这一步会确保新的排列更大。
[*]反转后部分：原来 i 处的元素已被替换为更大的元素；为了确保排列的字典序最小，反转 nums 到 nums 的部分，使得这一部分由降序变成升序，变成最小的排列。
为什么这样做是对的？
这是由字典序的性质决定的。每个排列在字典序中是由从左到右的逐步交换构成的。
[*]首先，从后向前找到不降序的第一个元素，确定了“还能增加”的部分。
[*]他应和之后最小的元素交换，并把其他元素重新变成正序，确保增加的字典序最小。
void nextPermutation(vector<int>& nums) {
int n = nums.size();
int i = n - 2;
while (i >= 0 && nums >= nums) i--;
if (i >= 0) swap(nums, nums);
reverse(nums.begin() + i + 1, nums.end());
}很多语言（也包括 C++）自带了此函数，复杂度显然是 \(O(n)\)。
全排列问题
全排列问题给定一个长度为 n 的数组，要求返回该数组的所有排列。比如，给定数组 ，我们要找出 、、、、、 这六个排列。
全排列的一个特点是，它会生成所有可能的排列组合，并且每个排列都包含数组中所有元素的不同顺序。全排列一共有 \(n!\) 个，你可以直接用上面的下一排列法枚举，运算量为 \(n! * n\)
另一个方案回溯法，通过递归的方式逐步填充排列中的每一个位置，并在每一步选择不同的元素，最后输出所有可能的排列。
[*]初始化：从空的排列开始，递归地填充每个位置。
[*]递归填充排列：每次递归时，我们按顺序在剩余未使用的数字中选择一个，并将其放入当前排列中，递归生成剩余的部分。
[*]回溯：当递归到达底部（即生成了一个排列），我们回到上一层，尝试其他选择。
[*]终止条件：当排列的长度等于数组的长度时，表示一个排列已完全生成，加入结果。
void permute(vector<int>& nums, vector<int>& path, vector<vector<int>>& result, vector<bool>& visited) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (visited) continue;
visited = true;
path.push_back(nums);
permute(nums, path, result, visited);
path.pop_back();
visited = false;
}
}
[*]时间复杂度：全排列问题的时间复杂度为 O(n!)，因为生成所有排列需要 n! 个排列，而每生成一个排列需要 O(n) 时间来复制和保存。
[*]空间复杂度：空间复杂度为 O(n)，递归深度。
拓展知识
排列顺序源于字典序，所以这种方法不仅适用于整数数组，也可以扩展到其他类型的数组（如字符串、字符等）。也并不要求数字是连续的 1 ~ n。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]