生成一个序列的所有排列，是算法练习和压力测试里经常遇到的一类需求。C++ 标准库没有直接返回排列集合的函数，但提供了 std::next_permutation，它可以把一个区间原地调整为字典序上的下一个排列。借助 do while 循环，只需要几行代码就能遍历完整排列。

这个函数位于 <algorithm> 头文件，常用形式是 std::next_permutation(first, last)。它返回 bool 值：如果还存在下一个更大的排列，就原地修改并返回 true；如果当前区间已经是降序，不存在下一个排列，就返回 false，同时把区间恢复为升序。这个重置行为很有用，意味着函数退出后容器仍保持一个确定状态，不会停留在半修改状态。

一、基础调用：用 do while 输出全排列

最典型的用法是先把容器排序，然后用 do while 反复调用 std::next_permutation，因为初始升序序列本身也是全排列中的第一个。下面这段代码会输出 {1,2,3} 的全部 6 个排列。

#include <iostream>
#include <algorithm>
#include <vector>
int main() {
    std::vector<int> v = {1, 2, 3};
    do {
        for (int x : v) {
            std::cout << x << ' ';
        }
        std::cout << '\n';
    } while (std::next_permutation(v.begin(), v.end()));
    return 0;
}

输出顺序是字典序：123、132、213、231、312、321。这里没有显式调用 sort，是因为 {1,2,3} 本身已经升序。实际使用时很多容器并不是升序，例如 {2,1,3} 如果直接进入循环，只会输出 213、231、312、321，前面的 123 和 132 会被漏掉。因此生成完整全排列前，应该先执行 std::sort(v.begin(), v.end())。

一次 next_permutation 的时间复杂度是线性级别，一般认为是 O(n)。如果枚举所有排列，总复杂度会达到 O(n·n!)，所以 n 通常控制在 10 到 12 以内比较现实。需要使用原序列时，最好复制一份再交给函数，因为函数会直接修改迭代器区间中的内容。

二、字典序工作原理与重复元素处理

理解下一个排列为什么是那个值，对调试很有帮助。标准库采用的算法并不神秘：先找到最靠右的一个相邻升序对，然后交换一个比它更大的元素，最后把尾部反转。以序列 [1,3,2] 为例，从右向左看，3 和 2 不是升序，继续向左，1 和 3 是升序，所以定位到 1。接着从右向左找到第一个大于 1 的元素，也就是 2，交换后得到 [2,3,1]。最后反转 [3,1] 部分变成 [2,1,3]，这正是 1,3,2 的下一个排列。

这个算法的思路是尽量保持前缀不变，只改变靠后的部分，从而保证新排列刚好比原来大。重复元素在这种基于比较的算法中天然会被跳过相同值，因为 1 和另一个 1 交换不会产生新的序列。例如字符串 abb 经过排序后调用 next_permutation，只会输出 abb、bab、bba 三个结果，而不会输出 6 个重复的伪排列。

#include <algorithm>
#include <iostream>
#include <string>
int main() {
    std::string s = "abb";
    std::sort(s.begin(), s.end());
    int count = 0;
    do {
        std::cout << s << '\n';
        ++count;
    } while (std::next_permutation(s.begin(), s.end()));
    std::cout << "count=" << count << '\n';
    return 0;
}

与手写深度优先搜索相比，这个函数天然处理重复元素，不需要额外地用 std::set 去重，也不需要在递归时判断相同值是否已经使用。只要初始排序正确，得到的结果数量就是数学意义上的排列数，避免漏解或多算。

三、自定义比较器：生成降序或任意规则排列

默认情况下，std::next_permutation 使用 operator<，也就是升序意义上的字典序。如果希望从大到小生成排列，可以传入 std::greater 作为比较器。比如要枚举 1 到 4 的降序全排列，初始排序也必须使用相同的比较器排序，否则同样会漏掉一部分结果。

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
int main() {
    std::vector<int> v = {1, 2, 3, 4};
    std::sort(v.begin(), v.end(), std::greater<int>());
    do {
        for (int x : v) {
            std::cout << x << ' ';
        }
        std::cout << '\n';
    } while (std::next_permutation(v.begin(), v.end(), std::greater<int>()));
    return 0;
}

这段代码会从 4321 开始，逐步生成到 1234，一共 24 个排列。比较器不限于 std::greater，任何满足严格弱序的规则都可以使用，例如按结构体某个字段排序，或者按字符串长度从短到长排列。但必须保证初始序列按同一规则排好，且比较规则稳定，否则 next_permutation 的行为会变得难以预测。

四、变体应用：用零一向量枚举组合

除了全排列，这个函数还能用来枚举组合。假设要从 n 个元素中选择 k 个，可以创建一个长度为 n 的选择向量，其中 k 个位置为 1，其余为 0。初始状态设为前面 n-k 个 0，后面 k 个 1，然后反复调用 next_permutation，直到这个向量变成前面 k 个 1，后面 n-k 个 0。

每次循环中，向量里 1 出现的位置就对应被选中的元素下标。下面代码从 5 个元素中选 3 个，并输出选中编号。

#include <algorithm>
#include <iostream>
#include <vector>
int main() {
    int n = 5;
    int k = 3;
    std::vector<int> select(n, 0);
    for (int i = n - k; i < n; ++i) {
        select[i] = 1; // 初始为 0 0 1 1 1
    }
    do {
        std::cout << "{ ";
        for (int i = 0; i < n; ++i) {
            if (select[i] == 1) {
                std::cout << i + 1 << ' ';
            }
        }
        std::cout << "}\n";
    } while (std::next_permutation(select.begin(), select.end()));
    return 0;
}

输出结果会按字典序逐一列出所有 C(5,3)=10 种组合，例如 { 3 4 5 }、{ 2 3 4 } 等。相比递归回溯，这种写法不需要维护栈和剪枝条件，也不容易在重复元素场景中犯错。当然，当 n 很大时组合数会急剧膨胀，仍然需要提前评估枚举成本。

总体来看，std::next_permutation 的核心优势在于原地操作、返回值和比较器重载。它既不是简单的排序工具，也不是只能生成全排列的专用函数，而是一个基于字典序的通用后继排列生成器。只要理解了排序前提和比较器规则，就能在排列、组合以及很多搜索场景中减少手写回溯的负担。