next_permutation生成序列的下一个排列

next_permutation 是 C++ 标准库 <algorithm> 中的一个函数，用于生成序列的下一个排列。它会按照字典序重新排列序列中的元素，并返回 true；如果当前序列已经是最后一个排列（即没有下一个排列），则返回 false。

next_permutation 的用法

函数原型

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

• 参数： first：指向序列起始位置的迭代器。last：指向序列结束位置的迭代器（指向最后一个元素的下一个位置）。
• 返回值： 如果存在下一个排列，返回 true，并将序列修改为下一个排列。如果当前序列已经是最后一个排列，返回 false，并将序列修改为第一个排列。

示例代码

以下是一个简单的示例，展示如何使用 next_permutation 生成所有排列：

#include <iostream>
#include <algorithm> // 包含 next_permutation
using namespace std;

int main() {
    int arr[] = {1, 2, 3}; // 初始序列
    int n = sizeof(arr) / sizeof(arr[0]); // 数组长度

    // 输出所有排列
    do {
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    } while (next_permutation(arr, arr + n)); // 生成下一个排列

    return 0;
}

输出：

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

关键点

1. 字典序：next_permutation 按照字典序生成排列。例如，{1, 2, 3} 的下一个排列是 {1, 3, 2}。如果当前序列是 {3, 2, 1}（字典序最后一个排列），调用 next_permutation 后会将其重置为 {1, 2, 3}，并返回 false。
2. 修改原序列：next_permutation 会直接修改原序列，生成下一个排列。
3. 适用性：适用于数组、vector 等支持随机访问的容器。元素需要支持 < 运算符（用于比较）。

在竞赛名次问题中的应用

在竞赛名次问题中，我们使用 next_permutation 枚举所有可能的名次排列（即 A、B、C、D 的所有排列），然后检查每种排列是否满足甲、乙、丙的预测条件。

代码片段

int ranks[4] = {1, 2, 3, 4}; // 名次排列
do {
    // 检查当前排列是否满足条件
    if (check(ranks, predictions)) {
        // 输出结果
        for (int i = 0; i < 4; i++) {
            cout << names[i] << " 第 " << ranks[i] << " 名" << endl;
        }
        break; // 找到一个解即可
    }
} while (next_permutation(ranks, ranks + 4)); // 生成下一个排列

总结

next_permutation 是一个非常强大的工具，特别适合用于需要枚举所有排列的问题（如逻辑推理、组合优化等）。它的时间复杂度为 (O(n)).