【STL】next_permutation 字典序排列函数

今天有刷题吗

1077人浏览 · 2025-05-06 15:11:52

今天有刷题吗 · 2025-05-06 15:11:52 发布

`next_permutation` 函数使用笔记

一、函数简介

next_permutation 是 C++ STL（Standard Template Library）中提供的一种非常有用的算法，用于生成给定序列的下一个字典序排列。

字典序排列是指按照某种顺序（通常是从小到大）对序列进行排列，就像字典中单词的排列顺序一样。例如，对于序列 [1, 2, 3]，其字典序排列依次为 [1, 2, 3]、[1, 3, 2]、[2, 1, 3]、[2, 3, 1]、[3, 1, 2] 和 [3, 2, 1]。

next_permutation 函数的作用是将当前序列调整为下一个字典序排列。如果当前序列已经是字典序中的最后一个排列（即按降序排列），则函数会将序列调整为字典序中的第一个排列（即按升序排列），并返回 false；否则返回 true。

二、函数原型

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

first 和 last 是双向迭代器，分别指向序列的起始位置和结束位置（不包括 last）。
函数返回值是一个布尔值，表示是否成功找到下一个字典序排列。

三、使用步骤

1. 包含头文件

next_permutation 函数定义在 <algorithm> 头文件中，因此在使用之前需要包含该头文件：

#include <algorithm>

2. 准备序列

可以使用数组、std::vector、std::list 等容器来存储序列。例如：

std::vector<int> vec = {1, 2, 3};

3. 调用函数

使用 next_permutation 函数对序列进行操作：

bool result = next_permutation(vec.begin(), vec.end());

如果 result 为 true，表示成功找到下一个字典序排列，vec 的内容会被更新为下一个排列。
如果 result 为 false，表示当前序列已经是字典序中的最后一个排列，vec 的内容会被更新为字典序中的第一个排列。

四、示例代码

示例 1：使用数组

#include <algorithm>
#include <iostream>

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    do {
        for (int i = 0; i < n; ++i) {
            std::cout << arr[i] << " ";
        }
        std::cout << std::endl;
    } while (next_permutation(arr, arr + n));

    return 0;
}

输出：

示例 2：使用 `std::vector`

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3};

    do {
        for (int num : vec) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    } while (next_permutation(vec.begin(), vec.end()));

    return 0;
}

输出与示例 1 相同。

五、注意事项

序列的初始状态
- 如果序列不是按字典序排列的，next_permutation 会直接生成下一个排列。
- 如果需要从字典序的第一个排列开始生成所有排列，建议先对序列进行升序排序，例如使用 std::sort。
```
std::sort(vec.begin(), vec.end());
```

自定义比较函数

如果需要对自定义类型或按照特定规则进行排列，可以提供一个自定义的比较函数作为第三个参数：

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

例如，按照降序生成排列：

std::vector<int> vec = {3, 2, 1};
do {
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
} while (next_permutation(vec.begin(), vec.end(), std::greater<int>()));

性能
- next_permutation 的时间复杂度为 O(n)，其中 n 是序列的长度。它通过局部调整序列来生成下一个排列，效率较高。
双向迭代器要求
- next_permutation 要求输入的迭代器是双向迭代器，这意味着它需要支持双向遍历（即向前和向后遍历）。因此，不能使用单向迭代器（如输入流迭代器）。