问询C++中next_permutation()函数的内部实现原理及代码

安全阿岳

2026-7-14

next_permutation 实现原理与代码

next_permutation 是C++标准库中生成字典序下一个排列的函数，核心逻辑基于字典序排列的生成规则，以下是详细原理和实现代码：

实现原理

生成下一个排列的核心步骤分为4步：

从序列末尾向前遍历，找到第一个满足 nums[i] < nums[i+1] 的索引 i（这个位置是排列中可以"增大"的起点）。如果遍历完整个序列都找不到这样的 i，说明当前是字典序的最后一个排列，函数返回false。
再次从序列末尾向前遍历，找到第一个大于 nums[i] 的元素索引 j（因为i+1到末尾是降序排列，第一个大于nums[i]的元素就是比它大的最小元素）。
交换 nums[i] 和 nums[j]，此时i位置的元素更新为更大的最小值，保证排列的字典序递增。
反转 i+1 到序列末尾的所有元素，交换后这部分仍为降序，反转后变为升序，得到当前i位置下最小的后续排列，即完整的下一个字典序排列。

手动实现代码

以下是和标准库行为一致的next_permutation实现（支持任意可随机访问的容器）：

#include <algorithm>
template <typename Iterator>
bool next_permutation(Iterator first, Iterator last) {
    if (first == last) return false;
    Iterator i = last;
    if (first == --i) return false;

    while (true) {
        Iterator i1 = i;
        if (*--i < *i1) {
            Iterator i2 = last;
            while (!(*i < *--i2));
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}