排列组合算法：next_permutation、prev_permutation与rotate
极难4玩转排列与旋转：next_permutation、prev_permutation和rotate入门
为什么要学这些算法？
想象你在玩一个数字锁——密码是三位数，每一位可以是1~3。为了暴力破解，你需要尝试所有可能的顺序（比如123、132、213…）。如果能把所有排列自动生成，就省去了手工列举的麻烦。next_permutation 和 prev_permutation 就是干这个的：它们可以按“字典序”一步步地生成下一个或上一个排列。
再比如，班里同学的座位要顺时针整体移动两个位置，你希望用一行代码完成循环移位。rotate 就是用来做这种“旋转”操作的——它像旋转木马一样，把一段元素从左到右或从右到左循环移动。
这些算法在游戏解法（如数独、八皇后）、密码爆破、数据轮转（如图片轮播、队列管理）中非常有用。即使你现在只是个小学生，也能体会到用程序自动列举所有排列的乐趣。
核心算法讲解
1. next_permutation —— 下一个更大的排列
它是干什么的？
给定一个序列（比如数组 {1,2,3}），它会把序列改成字典序中“下一个”更大的排列。如果当前已经是最大排列（降序，如{3,2,1}），就会变回最小排列（升序，如{1,2,3}）并返回 false；否则返回 true。
工作原理（通俗版）
假设你有一排卡片，上面写着数字。要把它们变成下一个更大的顺序，算法会先看最右边，找到第一个“倒置”的地方（比如从右向左找第一个比右边小的数），然后把它和右边最小的比它大的数交换，再把右边部分反转成升序。不过我们不需要自己实现，直接用就好。
前提条件
- 容器里的元素必须能用
<比较（数字、字符、字符串都可以）。 - 如果想枚举所有的排列，初始序列必须是升序（从小到大），否则只会枚举从当前状态往后的排列，会漏掉前面的。
用法示例
#include <iostream>
#include <vector>
#include <algorithm> // next_permutation
int main() {
// 初始数组，必须升序才能得到所有排列
std::vector<int> nums = {1, 2, 3}; // 升序
int count = 0; // 计数器
do {
std::cout << ++count << ": ";
for (int x : nums) std::cout << x << " ";
std::cout << std::endl;
} while (std::next_permutation(nums.begin(), nums.end()));
// 输出6种排列（3! = 6）
return 0;
}
输出
1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1
2. prev_permutation —— 上一个更小的排列
它是干什么的？
与 next_permutation 相反，它会生成字典序中“上一个”排列。如果当前已经是最小排列（升序），就变为最大排列（降序）并返回 false。
使用技巧
如果要枚举所有逆序排列（从大到小），可以先把序列降序排序，然后用 prev_permutation。
用法示例
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> nums = {3, 2, 1}; // 降序，才能得到所有逆序排列
int count = 0;
do {
std::cout << ++count << ": ";
for (int x : nums) std::cout << x << " ";
std::cout << std::endl;
} while (std::prev_permutation(nums.begin(), nums.end()));
// 输出6种排列（同样是全排列，但顺序是逆字典序）
return 0;
}
输出
1: 3 2 1
2: 3 1 2
3: 2 3 1
4: 2 1 3
5: 1 3 2
6: 1 2 3
3. rotate —— 循环移位（旋转）
它是干什么的？
把一段区间 [first, last) 以 middle 为分界，把前半部分 [first, middle) 移到末尾，后半部分 [middle, last) 移到前面，相当于整体向左旋转（如果你把 middle 看成新序列的第一个元素）。
生活中的例子
- 排队时老师喊“全体向左转90度”，同学顺序变了，但相对位置没变。
- 手机屏幕旋转：比如把照片顺时针旋转90度。
- 轮转数组：比如数组 [1,2,3,4,5,6] 左移2位变成 [3,4,5,6,1,2]。
用法
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7};
// 左移2位：把前2个元素移到末尾
std::rotate(v.begin(), v.begin() + 2, v.end());
// 输出：3 4 5 6 7 1 2
for (int x : v) std::cout << x << " ";
return 0;
}
右移怎么做？
右移相当于把末尾的几个元素移到前面，可以通过左移（size - k）位来实现。例如右移3位，等价于左移 7 - 3 = 4 位：
// 右移3位
int k = 3;
std::rotate(v.begin(), v.begin() + (v.size() - k), v.end());
// 结果：5 6 7 1 2 3 4
时间复杂度
rotate 是原地操作，时间复杂度 O(n)，不需要额外空间，非常高效。
常见错误与新手陷阱
1. 忘记初始化排序导致漏掉排列
// 错误例子
std::vector<int> v = {2, 1, 3}; // 不是升序，从{2,1,3}开始next_permutation
do { /* 处理 */ } while (std::next_permutation(v.begin(), v.end()));
// 结果只会输出：2 1 3 → 2 3 1 → 3 1 2 → 3 2 1，少了 {1,2,3} 和 {1,3,2}
正确做法：如果要用 next_permutation 枚举所有排列，先排序：
std::sort(v.begin(), v.end());
2. 混淆左移和右移时的 middle
rotate 的第二个参数是新序列的第一个元素。左移2位，新开头是 begin()+2；右移3位，新开头是 begin() + (size - 3)。很多人会写反，导致旋转错误。
3. 认为 next_permutation 会改变原容器并返回新容器
实际上它是原地修改，不是返回新容器。所以如果你想保留原数据，必须先复制一份。
std::vector<int> original = {1,2,3};
auto copy = original;
std::next_permutation(original.begin(), original.end());
// 此时 original 被修改，copy 仍是原值
4. 对字符数组或字符串使用时忽略大小写
字符的字典序取决于 ASCII 码，大写字母（A=65）比小写字母（a=97）小。如果你排序时大小写混用，排列结果可能不符合预期。
完整可运行代码示例（C++）
下面是一个综合例子，展示了三个算法的用法，并在每行变量定义后添加了中文注释。
#include <iostream>
#include <vector>
#include <algorithm> // next_permutation, prev_permutation, rotate
#include <string>
#include <numeric> // iota 方便生成连续数字
// 打印容器的工具函数
void printVector(const std::string& msg, const std::vector<int>& v) {
std::cout << msg;
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
}
int main() {
// ---------- 1. next_permutation：生成所有排列 ----------
std::vector<int> nums = {1, 2, 3}; // 初始数组（升序）
std::cout << "所有排列（字典序递增）：" << std::endl;
int count = 0; // 排列序号
do {
std::cout << ++count << ": ";
for (int x : nums) std::cout << x << " ";
std::cout << std::endl;
} while (std::next_permutation(nums.begin(), nums.end()));
// ---------- 2. prev_permutation：从降序开始生成所有排列 ----------
std::vector<int> nums2 = {3, 2, 1}; // 初始数组（降序）
std::cout << "\n所有排列（字典序递减）：" << std::endl;
count = 0; // 重置计数器
do {
std::cout << ++count << ": ";
for (int x : nums2) std::cout << x << " ";
std::cout << std::endl;
} while (std::prev_permutation(nums2.begin(), nums2.end()));
// ---------- 3. 字符串排列 ----------
std::string s = "ABC"; // 初始字符串
std::cout << "\n字符串排列：";
do {
std::cout << s << " ";
} while (std::next_permutation(s.begin(), s.end()));
std::cout << std::endl;
// ---------- 4. rotate 旋转 ----------
std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7}; // 原始数组
printVector("原始：", vec);
// 左移2位（相当于旋转使得第3个元素变成新开头）
std::rotate(vec.begin(), vec.begin() + 2, vec.end());
printVector("左移2位：", vec); // 输出：3 4 5 6 7 1 2
// 右移3位（通过左移 size-3 位实现）
vec = {1, 2, 3, 4, 5, 6, 7}; // 重置为原始
int k = 3; // 右移位数
std::rotate(vec.begin(), vec.begin() + (vec.size() - k), vec.end());
printVector("右移3位：", vec); // 输出：5 6 7 1 2 3 4
return 0;
}
运行结果
所有排列（字典序递增）：
1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1
所有排列（字典序递减）：
1: 3 2 1
2: 3 1 2
3: 2 3 1
4: 2 1 3
5: 1 3 2
6: 1 2 3
字符串排列：ABC ACB BAC BCA CAB CBA
原始：1 2 3 4 5 6 7
左移2位：3 4 5 6 7 1 2
右移3位：5 6 7 1 2 3 4
Python 等价功能（及注释）
Python 的 itertools 模块非常强大，但用法与 C++ 不同。permutations 会生成所有排列的迭代器，不会修改原列表；rotate 可以用切片轻松实现。
import itertools
# ---------- 1. next_permutation 等价：使用 itertools.permutations ----------
print("所有排列（从最小开始）：")
numbers = [1, 2, 3] # 初始列表
for count, perm in enumerate(itertools.permutations(numbers), 1):
print(f"{count}: {list(perm)}")
# ---------- 2. 逆字典序排列 ----------
# 如果要降序排列，可以对结果列表排序
print("\n所有排列（字典序递减）：")
all_perms = list(itertools.permutations([3, 2, 1])) # 生成所有排列
sorted_perms = sorted(all_perms, reverse=True) # 按字典序降序排序
for count, perm in enumerate(sorted_perms, 1):
print(f"{count}: {list(perm)}")
# ---------- 3. 字符串排列 ----------
s = "ABC"
print("\n字符串排列：")
for perm in itertools.permutations(s):
print(''.join(perm), end=' ')
print()
# ---------- 4. rotate 旋转（用切片实现） ----------
vec = [1, 2, 3, 4, 5, 6, 7] # 原始列表
print("原始:", vec)
# 左移2位
rotated_left = vec[2:] + vec[:2] # 切片生成新列表
print("左移2位:", rotated_left)
# 右移3位
k = 3
rotated_right = vec[-k:] + vec[:-k] # 负索引取末尾k个元素
print("右移3位:", rotated_right)
重要区别
itertools.permutations默认按输入元素的原顺序生成排列，如果输入是[3,2,1]，它生成的第一个排列是(3,2,1)，第二个是(3,1,2)，而不是严格的字典序递增。要获得严格字典序，需要先对输入排序（sorted）后再生成。- 另外，如果列表中有重复元素（比如
[1,1,2]），permutations会把两个1视为不同对象，导致结果中有重复排列。要得到无重复排列，可以用set或itertools.permutations后用集合去重。 rotate在 Python 中用切片会产生新列表（O(n)空间），而 C++ 的rotate是原地修改，节省内存。
总结与进阶方向
- next_permutation / prev_permutation：适合需要按顺序枚举所有排列的场景，初始序列必须是有序的（升序/降序）。注意它们会原地修改容器。
- rotate：高效的循环移位，一次 O(n)，原地操作。可用于数组轮转、循环队列、加密算法中的位旋转等。
- 常见错误：
- 忘记排序导致排列不全。
- 在非升序序列上使用
next_permutation时，认为能得到所有排列。 - 混淆
rotate的参数顺序（first, middle, last），记不住哪个是新开头。
掌握了这些，你就可以在更多场合玩转顺序变换。如果想进一步了解，可以查看：
- std::sort（排序是排列的起点）
- std::reverse（反转区间）
- std::shuffle（随机打乱，类似洗牌）
- 组合数枚举（有时我们需要组合而不是排列，可以用
std::next_combination或自己实现）
让计算机自动生成所有可能的顺序，是不是很酷？快去试试吧！
例题精讲
在使用 std::next_permutation 生成所有排列时，为了确保能枚举出所有可能的排列，对初始序列的要求是什么？
使用 std::prev_permutation 时，如果当前序列已经是字典序最小的排列，则函数返回 false 并将序列重置为字典序最大的排列。
以下代码使用 std::next_permutation 打印一个数组的所有排列，请补全空白部分。#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> v = {3, 1, 2};
___;
do {
for (int x : v) cout << x << ' ';
cout << endl;
} while (___);
return 0;
}已知 vector<int> v = {10, 20, 30, 40, 50}，执行 std::rotate(v.begin(), v.begin() + 2, v.end()) 后，v 中的元素顺序变为：
std::next_permutation 和 std::prev_permutation 的时间复杂度均为 O(n)，其中 n 为序列长度，且它们在处理每个排列时平均只需要常数次交换。