在一个排列集合中，寻找某一个排列 $P\_i$ 的下一个字典序排列 $P\_{i+1}$ 是一个经典的组合数学与算法问题。著名的“下一个排列”（Next Permutation）算法（在 C++ 标准库中实现为 `std::next_permutation`）正是解决这一问题的最优方法。

该算法本质上利用了**贪心策略**来最小化排列变化的幅度。以下为您提供该问题的数学模型、贪心算法的设计、数学证明以及基于 C++11 的代码实现。

---

### 一、 数学模型与问题定义

#### 1. 字典序的定义
设有两个长度为 $n$ 的排列 $A = (a\_1, a\_2, \dots, a\_n)$ 和 $B = (b\_1, b\_2, \dots, b\_n)$。
称 $B$ 的字典序大于 $A$（记作 $B > A$），当且仅当存在一个索引 $i \in [1, n]$，满足：
* 对于所有 $1 \le j < i$，有 $b\_j = a\_j$；
* 且 $b\_i > a\_i$。

#### 2. 问题目标
给定当前排列 $P\_i$，我们需要找到一个排列 $P\_{i+1}$，使得：
1. $P\_{i+1} > P\_i$
2. 不存在任何排列 $Q$，满足 $P\_{i+1} > Q > P\_i$。

即 $P\_{i+1}$ 是严格大于 $P\_i$ 的所有排列中字典序最小的那一个（即紧随其后的下一个排列）。

---

### 二、 贪心算法步骤

为了使增幅最小，我们需要**贪心地保留尽可能长的公共前缀**，并对后缀进行最小幅度的调整。

设当前排列为 $A = (a\_1, a\_2, \dots, a\_n)$：
1. **寻找转折点（Pivot）**：从右向左遍历，找到第一个满足 $a\_k < a\_{k+1}$ 的位置 $k$。
   * 如果不存在这样的 $k$（即整个序列是单调递减的），说明当前排列已经是最大的排列，没有下一个排列（通常可以将其翻转为升序，回到最小排列）。
2. **寻找替换数**：在区间 $[k+1, n]$ 中，从右向左寻找第一个满足 $a\_l > a\_k$ 的位置 $l$。由于 $a[k+1 \dots n]$ 是单调递减的，这个 $a\_l$ 必然是该区间内**大于 $a\_k$ 的最小数**。
3. **交换**：交换 $a\_k$ 与 $a\_l$。
4. **逆序恢复**：将区间 $a[k+1 \dots n]$ 逆序（由于原本是递减的，逆序后将变成递增的）。

---

### 三、 数学证明

为了证明上述算法产生的 $P\_{i+1}$ 确实是 $P\_i$ 的紧邻下一个排列，我们需要证明两个核心命题。

#### 命题 1：为什么要找到最右侧的 $a\_k < a\_{k+1}$？
**证明**：
根据字典序定义，要让排列变大，我们必须改变某处的字符，使其变大。
若我们改变位置 $i$ 处的字符，将其替换为一个更大的字符，那么为了保持前缀尽可能一致（即变化最小），我们应该让这个修改发生的位置 $i$ 尽可能靠右。
如果一个后缀 $a[k+1 \dots n]$ 是单调递减的，那么根据排列组合原理，该后缀已经是当前这些元素所能组成的最大字典序子排列。在不修改 $a\_1 \dots a\_k$ 的情况下，我们无法通过重排后缀来获得更大的排列。
因此，必须修改更靠左的元素。最靠右的、能够通过重排后缀使其变大的位置，就是满足 $a\_k < a\_{k+1}$ 的最大索引 $k$。保持前缀 $a\_1 \dots a\_{k-1}$ 不变是贪心策略的核心。

#### 命题 2：交换 $a\_k$ 与 $a\_l$ 并逆序后，所得排列是最小的“大于 $P\_i$ 的排列”。
**证明**：
1. **替换 $a\_k$ 的选择**：
   为了使新的排列大于原排列，新位置 $k$ 的元素 $a'\_k$ 必须大于原 $a\_k$。为了让增幅最小，在后缀 $a[k+1 \dots n]$ 中，我们必须选择**大于 $a\_k$ 的最小元素**来替换它。
   因为 $a[k+1 \dots n]$ 是单调递减的，从右往左第一个大于 $a\_k$ 的元素 $a\_l$ 恰好就是该区间内大于 $a\_k$ 的最小元素。

2. **交换后的后缀性质**：
   在交换 $a\_k$ 与 $a\_l$ 之前，后缀满足：
   $$a\_{k+1} \ge a\_{k+2} \ge \dots \ge a\_l \ge \dots \ge a\_n$$
   交换后，原 $a\_l$ 位置变为了 $a\_k$。我们检查交换后的后缀：
   * 对于 $j > l$，元素未变，单调性保持。
   * 对于 $j = l$，由于 $a\_l$ 是从右往左第一个大于 $a\_k$ 的数，说明 $a\_{l+1} \le a\_k$。因此交换后仍然满足 $a\_k \ge a\_{l+1}$。
   * 对于 $j < l$，由于 $a\_l > a\_k$，因此原序列中的 $a\_{l-1} \ge a\_l > a\_k$，交换后仍满足 $a\_{l-1} \ge a\_k$。
   综上所述，交换后的新后缀依然保持**单调递减**。

3. **逆序的合理性**：
   为了使整个排列在保证前缀 $a'\_1 \dots a'\_k$ 确定的情况下字典序最小，后缀 $a'[k+1 \dots n]$ 必须处于其**最小字典序**状态（即单调递增）。
   既然当前的后缀已经是单调递减的，我们只需要将其完全逆序（Reverse），即可在 $O(n - k)$ 的时间内将其转化为单调递增，从而获得最小的后半部分。

由于前缀最小化了改变位置，转折点最小化了数值增幅，后缀达到了最小字典序，因此该算法推导出的排列必然是紧邻的下一个排列 $P\_{i+1}$。

---

### 四、 C++11 代码实现

以下是符合 C++11 标准的实现。我们不直接调用 `std::next_permutation`，而是手动实现其核心逻辑，以便展示上述数学模型的每一个步骤：

```cpp
#include <iostream>
#include <vector>
#include <algorithm>

/**
 * @brief 获取当前排列的下一个字典序排列
 * @tparam T 元素类型
 * @param nums 待求下一排列的数组
 * @return bool 如果存在下一个排列返回 true，若已经是最大排列则重置为最小排列并返回 false
 */
template <typename T>
bool next_permutation_custom(std::vector<T>& nums) noexcept {
    if (nums.empty() || nums.size() == 1) {
        return false;
    }

// 1. 从右向左寻找第一个降序相邻对 (k, k + 1)，即满足 nums[k] < nums[k + 1]
    auto k_it = nums.end() - 2;
    while (k_it >= nums.begin() && *k_it >= *(k_it + 1)) {
        --k_it;
    }

// 如果不存在这样的 k，说明当前排列已是最大（单调递减）
    if (k_it < nums.begin()) {
        std::reverse(nums.begin(), nums.end()); // 翻转为最小排列
        return false;
    }

// 2. 从右向左在区间 [k + 1, end) 中寻找第一个大于 nums[k] 的元素 nums[l]
    auto l_it = nums.end() - 1;
    while (l_it > k_it && *l_it <= *k_it) {
        --l_it;
    }

// 3. 交换 nums[k] 与 nums[l]
    std::swap(*k_it, *l_it);

// 4. 将区间 [k + 1, end) 逆序，使其变为升序（最小化后缀）
    std::reverse(k_it + 1, nums.end());

return true;
}

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

std::cout << "当前排列: ";
    for (int num : p) std::cout << num << " ";
    std::cout << "\n\n";

std::cout << "生成后续所有排列:\n";
    // 循环打印接下来的排列，直到回到初始状态
    do {
        for (int num : p) {
            std::cout << num << " ";
        }
        std::cout << "\n";
    } while (next_permutation_custom(p));

return 0;
}
```

### 复杂度分析
* **时间复杂度**：$O(n)$。在最坏情况下，我们需要扫描整个数组两次（一次找 $k$，一次找 $l$），并对后缀进行一次逆序操作。所有操作的时间复杂度均为线性。
* **空间复杂度**：$O(1)$。算法在原数组上进行原地（In-place）交换与逆序，仅需要常数级别的辅助变量。

在一个排列集合中，寻找某一个排列 $P_i$ 的下一个字典序排列 $P_{i+1}$ 是一个经典的组合数学与算法问题。著名的“下一个排列”（Next Permutation）算法（在 C++ 标准库中实现为 std::next_permutation）正是解决这一问题的最优方法。

该算法本质上利用了贪心策略来最小化排列变化的幅度。以下为您提供该问题的数学模型、贪心算法的设计、数学证明以及基于 C++11 的代码实现。

一、数学模型与问题定义

1. 字典序的定义

设有两个长度为 $n$ 的排列 $A = (a_1, a_2, \dots, a_n)$ 和 $B = (b_1, b_2, \dots, b_n)$。称 $B$ 的字典序大于 $A$（记作 $B > A$），当且仅当存在一个索引 $i \in [1, n]$，满足： * 对于所有 $1 \le j < i$，有 $b_j = a_j$； * 且 $b_i > a_i$。

2. 问题目标

给定当前排列 $P_i$，我们需要找到一个排列 $P_{i+1}$，使得： 1. $P_{i+1} > P_i$ 2. 不存在任何排列 $Q$，满足 $P_{i+1} > Q > P_i$。

即 $P_{i+1}$ 是严格大于 $P_i$ 的所有排列中字典序最小的那一个（即紧随其后的下一个排列）。

二、贪心算法步骤

为了使增幅最小，我们需要贪心地保留尽可能长的公共前缀，并对后缀进行最小幅度的调整。

设当前排列为 $A = (a_1, a_2, \dots, a_n)$： 1. 寻找转折点（Pivot）：从右向左遍历，找到第一个满足 $a_k < a_{k+1}$ 的位置 $k$。 * 如果不存在这样的 $k$（即整个序列是单调递减的），说明当前排列已经是最大的排列，没有下一个排列（通常可以将其翻转为升序，回到最小排列）。 2. 寻找替换数：在区间 $[k+1, n]$ 中，从右向左寻找第一个满足 $a_l > a_k$ 的位置 $l$。由于 $a[k+1 \dots n]$ 是单调递减的，这个 $a_l$ 必然是该区间内大于 $a_k$ 的最小数。 3. 交换：交换 $a_k$ 与 $a_l$。 4. 逆序恢复：将区间 $a[k+1 \dots n]$ 逆序（由于原本是递减的，逆序后将变成递增的）。

三、数学证明

为了证明上述算法产生的 $P_{i+1}$ 确实是 $P_i$ 的紧邻下一个排列，我们需要证明两个核心命题。

命题 1：为什么要找到最右侧的 $a_k < a_{k+1}$？

证明：根据字典序定义，要让排列变大，我们必须改变某处的字符，使其变大。若我们改变位置 $i$ 处的字符，将其替换为一个更大的字符，那么为了保持前缀尽可能一致（即变化最小），我们应该让这个修改发生的位置 $i$ 尽可能靠右。如果一个后缀 $a[k+1 \dots n]$ 是单调递减的，那么根据排列组合原理，该后缀已经是当前这些元素所能组成的最大字典序子排列。在不修改 $a_1 \dots a_k$ 的情况下，我们无法通过重排后缀来获得更大的排列。因此，必须修改更靠左的元素。最靠右的、能够通过重排后缀使其变大的位置，就是满足 $a_k < a_{k+1}$ 的最大索引 $k$。保持前缀 $a_1 \dots a_{k-1}$ 不变是贪心策略的核心。

命题 2：交换 $a_k$ 与 $a_l$ 并逆序后，所得排列是最小的“大于 $P_i$ 的排列”。

证明： 1. 替换 $a_k$ 的选择：为了使新的排列大于原排列，新位置 $k$ 的元素 $a'_k$ 必须大于原 $a_k$。为了让增幅最小，在后缀 $a[k+1 \dots n]$ 中，我们必须选择大于 $a_k$ 的最小元素来替换它。因为 $a[k+1 \dots n]$ 是单调递减的，从右往左第一个大于 $a_k$ 的元素 $a_l$ 恰好就是该区间内大于 $a_k$ 的最小元素。

交换后的后缀性质：在交换 $a_k$ 与 $a_l$ 之前，后缀满足： $$a_{k+1} \ge a_{k+2} \ge \dots \ge a_l \ge \dots \ge a_n$$ 交换后，原 $a_l$ 位置变为了 $a_k$。我们检查交换后的后缀：
对于 $j > l$，元素未变，单调性保持。
对于 $j = l$，由于 $a_l$ 是从右往左第一个大于 $a_k$ 的数，说明 $a_{l+1} \le a_k$。因此交换后仍然满足 $a_k \ge a_{l+1}$。
对于 $j < l$，由于 $a_l > a_k$，因此原序列中的 $a_{l-1} \ge a_l > a_k$，交换后仍满足 $a_{l-1} \ge a_k$。综上所述，交换后的新后缀依然保持单调递减。
逆序的合理性：为了使整个排列在保证前缀 $a'_1 \dots a'_k$ 确定的情况下字典序最小，后缀 $a'[k+1 \dots n]$ 必须处于其最小字典序状态（即单调递增）。既然当前的后缀已经是单调递减的，我们只需要将其完全逆序（Reverse），即可在 $O(n - k)$ 的时间内将其转化为单调递增，从而获得最小的后半部分。

由于前缀最小化了改变位置，转折点最小化了数值增幅，后缀达到了最小字典序，因此该算法推导出的排列必然是紧邻的下一个排列 $P_{i+1}$。

四、 C++11 代码实现

以下是符合 C++11 标准的实现。我们不直接调用 std::next_permutation，而是手动实现其核心逻辑，以便展示上述数学模型的每一个步骤：

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

/**
 * @brief 获取当前排列的下一个字典序排列
 * @tparam T 元素类型
 * @param nums 待求下一排列的数组
 * @return bool 如果存在下一个排列返回 true，若已经是最大排列则重置为最小排列并返回 false
 */
template <typename T>
bool next_permutation_custom(std::vector<T>& nums) noexcept {
    if (nums.empty() || nums.size() == 1) {
        return false;
    }

    // 1. 从右向左寻找第一个降序相邻对 (k, k + 1)，即满足 nums[k] < nums[k + 1]
    auto k_it = nums.end() - 2;
    while (k_it >= nums.begin() && *k_it >= *(k_it + 1)) {
        --k_it;
    }

    // 如果不存在这样的 k，说明当前排列已是最大（单调递减）
    if (k_it < nums.begin()) {
        std::reverse(nums.begin(), nums.end()); // 翻转为最小排列
        return false;
    }

    // 2. 从右向左在区间 [k + 1, end) 中寻找第一个大于 nums[k] 的元素 nums[l]
    auto l_it = nums.end() - 1;
    while (l_it > k_it && *l_it <= *k_it) {
        --l_it;
    }

    // 3. 交换 nums[k] 与 nums[l]
    std::swap(*k_it, *l_it);

    // 4. 将区间 [k + 1, end) 逆序，使其变为升序（最小化后缀）
    std::reverse(k_it + 1, nums.end());

    return true;
}

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

    std::cout << "当前排列: ";
    for (int num : p) std::cout << num << " ";
    std::cout << "\n\n";

    std::cout << "生成后续所有排列:\n";
    // 循环打印接下来的排列，直到回到初始状态
    do {
        for (int num : p) {
            std::cout << num << " ";
        }
        std::cout << "\n";
    } while (next_permutation_custom(p));

    return 0;
}

复杂度分析

时间复杂度：$O(n)$。在最坏情况下，我们需要扫描整个数组两次（一次找 $k$，一次找 $l$），并对后缀进行一次逆序操作。所有操作的时间复杂度均为线性。
空间复杂度：$O(1)$。算法在原数组上进行原地（In-place）交换与逆序，仅需要常数级别的辅助变量。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

下一个排列

一、 数学模型与问题定义