字典序排列算法：高效求解上一个排列问题

1. 项目概述

"3335：【例57.2】 上一个排列"这个标题看起来像是一个算法练习题或者编程竞赛中的题目编号。从标题可以判断，这是一个关于排列组合的算法问题，具体来说是需要找到给定排列在字典序中的前一个排列（即"上一个排列"）。

这类问题在编程面试和算法竞赛中非常常见，属于排列组合和搜索算法的基础题型。掌握这类问题的解法不仅能帮助我们理解排列的生成机制，还能培养解决更复杂组合问题的思维能力。

2. 问题理解与定义

2.1 排列的字典序

在讨论"上一个排列"之前，我们需要明确什么是排列的字典序。字典序（lexicographical order）是指按照字母表顺序排列的顺序。对于数字排列来说，可以类比为数字组成的"单词"在字典中的排列顺序。

例如，对于数字1,2,3的所有排列，按字典序排列如下：

1. 1,2,3
2. 1,3,2
3. 2,1,3
4. 2,3,1
5. 3,1,2
6. 3,2,1

2.2 上一个排列的定义

给定一个排列，它的"上一个排列"是指在字典序中恰好位于它前面的那个排列。如果当前排列已经是字典序中的第一个排列（即完全升序排列），则它没有上一个排列。

例如：

• 对于排列[1,3,2]，它的上一个排列是[1,2,3]
• 对于排列[3,2,1]，它的上一个排列是[3,1,2]
• 对于排列[1,2,3]，它没有上一个排列

3. 算法设计与思路

3.1 暴力解法

最直观的解法是生成所有可能的排列，按字典序排序，然后找到当前排列的前一个。这种方法虽然简单，但时间复杂度极高（O(n!)），对于较大的n完全不实用。

3.2 高效算法思路

我们需要找到一个更高效的算法，能够在O(n)时间内解决问题。观察字典序中排列的变化规律，可以发现：

1. 上一个排列通常是通过将当前排列中的某个元素与它前面的某个较小元素交换得到的
2. 交换后，交换点后面的部分需要重新排列为降序，以得到最大的可能排列（即上一个排列）

具体步骤如下：

1. 从后向前查找第一个升序对(i, i+1)，即nums[i] > nums[i+1]
2. 如果找不到这样的对，说明当前排列已经是第一个排列，返回空或特定值
3. 从后向前查找第一个小于nums[i]的元素nums[j]
4. 交换nums[i]和nums[j]
5. 将i+1到末尾的部分反转（即变为降序）

3.3 算法正确性证明

这个算法的正确性基于字典序的定义。通过找到第一个可以减小的位置（i），然后在该位置后面找到最大的可能减小的值（j），最后将后面部分变为最大可能排列（降序），我们就能确保得到的是严格的上一个排列。

4. 代码实现与解析

4.1 C++实现

cpp复制#include <vector>
#include <algorithm>

using namespace std;

void prevPermutation(vector<int>& nums) {
    int n = nums.size();
    int i = n - 2;
    
    // 步骤1：从后向前找第一个升序对
    while (i >= 0 && nums[i] <= nums[i + 1]) {
        i--;
    }
    
    if (i >= 0) {
        int j = n - 1;
        // 步骤2：从后向前找第一个小于nums[i]的数
        while (j >= 0 && nums[j] >= nums[i]) {
            j--;
        }
        // 步骤3：交换
        swap(nums[i], nums[j]);
    }
    // 步骤4：反转i+1到末尾
    reverse(nums.begin() + i + 1, nums.end());
}

4.2 Python实现

python复制def prev_permutation(nums):
    n = len(nums)
    i = n - 2
    
    # 步骤1：从后向前找第一个升序对
    while i >= 0 and nums[i] <= nums[i + 1]:
        i -= 1
    
    if i >= 0:
        j = n - 1
        # 步骤2：从后向前找第一个小于nums[i]的数
        whil