next_permutation 是 C++ 标准库 <algorithm> 中的一个函数，用于对序列生成下一个字典序排列。如果当前序列已经是字典序的最后一个排列，则生成第一个排列（即最小的排列）。
基本用法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3};
do {
for (int x : vec)
std::cout << x << " ";
std::cout << "\n";
} while (std::next_permutation(vec.begin(), vec.end()));
return 0;
}
|
特点和注意事项
- 返回值：
next_permutation 返回一个布尔值。如果成功生成下一个排列，返回 true；如果已经是最后一个排列并生成了第一个排列，返回 false。
- 原地操作：
next_permutation 对传入的序列进行原地重排，不会分配额外的内存。
- 序列要求：适用于任何支持随机访问迭代器的序列，如
std::vector、std::array、原始数组等。
- 算法复杂度：在最坏情况下，
next_permutation 的时间复杂度是 O(N)，其中 N 是序列的长度。
示例代码
下面是一个更详细的示例，演示了 next_permutation 的使用，并说明了如何在不同的数据类型上应用：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3};
std::cout << "整数向量的排列:\n";
do {
for (int x : vec)
std::cout << x << " ";
std::cout << "\n";
} while (std::next_permutation(vec.begin(), vec.end()));
char arr[] = {'a', 'b', 'c'};
std::cout << "\n字符数组的排列:\n";
do {
for (char x : arr)
std::cout << x << " ";
std::cout << "\n";
} while (std::next_permutation(arr, arr + 3));
return 0;
}
|
在这个示例中，我们分别对整数向量和字符数组进行了排列。使用 next_permutation 函数可以方便地生成序列的所有排列，并进行处理或输出。需要注意的是，如果需要生成排列的序列是已排序的，那么第一次调用 next_permutation 将生成其下一个字典序排列，否则可能需要多次调用才能达到效果。