C++ 第58题：std::next_permutation 与 std::prev_permutation 全排列生成算法

题目

编写程序，使用 std::next_permutation 算法以字典序生成指定集合的所有全排列。掌握该算法的两个关键前置条件：①生成完整全排列前序列必须预先按升序排好；②当遍历到达字典序最大排列时算法返回 false 并将序列重置为最小升序。随后展示逆向全排列 std::prev_permutation。

输入格式：无需外部输入。

输出格式：依次打印由字典序生成的全排列总数与所有排列组合详情。

数据范围与约定：全排列组合算法、字典序推进数学原理。

思路与算法

1. 字典序推进算法原理
next_permutation 内部算法步骤：①从后向前找到第一个破坏升序的转折点 \(i\)；②在 \(i\) 右侧找到大于元素 \(i\) 的最小数 \(j\) 并交换；③将 \(i\) 右侧的剩余序列翻转（从降序变升序）。全过程时间均摊 O(1)！

2. 必须先排升序
如果原数组未排序（如初始输入为 {3, 1, 2}），next_permutation 只能生成其字典序之后的后继排列，会导致字典序小于它的排列（如 {1, 2, 3}）全部遗漏。

3. 支持重复元素
该算法天然支持含有重复元素的集合，能够自动生成不重复的组合全排列。

完整程序

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

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

    // 关键第一步：为了完整生成全排列，必须先排成升序
    std::sort(nums.begin(), nums.end());

    std::cout << "--- 1. std::next_permutation 升序生成所有全排列 ---\n";
    int count = 0;
    do {
        std::cout << "排列 #" << ++count << ": [ ";
        for (int x : nums) {
            std::cout << x << " ";
        }
        std::cout << "]\n";
    } while (std::next_permutation(nums.begin(), nums.end()));

    std::cout << "合计生成全排列数: " << count << " 组 (3! = 6)\n\n";

    // 2. 逆向：从降序序列开始使用 std::prev_permutation
    std::vector<char> letters = {'c', 'b', 'a'};
    std::cout << "--- 2. std::prev_permutation 降序回退全排列 ---\n";
    do {
        std::cout << letters[0] << letters[1] << letters[2] << " ";
    } while (std::prev_permutation(letters.begin(), letters.end()));
    std::cout << "\n";

    return 0;
}

运行示例

输出：

--- 1. std::next_permutation 升序生成所有全排列 ---
排列 #1: [ 1 2 3 ]
排列 #2: [ 1 3 2 ]
排列 #3: [ 2 1 3 ]
排列 #4: [ 2 3 1 ]
排列 #5: [ 3 1 2 ]
排列 #6: [ 3 2 1 ]
合计生成全排列数: 6 组 (3! = 6)

--- 2. std::prev_permutation 降序回退全排列 ---
cba cab bca bac acb abc