Python实现在STL next_permutation

Python实现STL的next_permutation功能

基础概念

next_permutation是C++标准模板库(STL)中的一个算法函数，用于生成序列的下一个字典序排列。它会原地修改序列，使其成为下一个更大的排列。如果当前序列已经是最大排列(降序排列)，则将其变为最小排列(升序排列)并返回false。

Python实现原理

Python可以通过以下步骤实现类似功能：

从序列末尾向前查找第一个下降点(即找到第一个nums[i] < nums[i+1]的位置)
如果找不到这样的点，说明整个序列是降序排列，已经是最大排列，将其反转得到最小排列
否则，从末尾向前查找第一个大于nums[i]的元素nums[j]
交换nums[i]和nums[j]
反转nums[i+1:]部分

完整Python实现代码

def next_permutation(nums):
    """
    实现类似C++ STL的next_permutation功能
    :param nums: 可变的序列(列表)
    :return: 如果生成了下一个排列返回True，如果已经是最大排列返回False
    """
    n = len(nums)
    if n <= 1:
        return False
    
    # 步骤1: 从后向前找到第一个下降点
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    
    if i >= 0:
        # 步骤2: 从后向前找到第一个大于nums[i]的元素
        j = n - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        # 步骤3: 交换这两个元素
        nums[i], nums[j] = nums[j], nums[i]
    
    # 步骤4: 反转i+1到末尾的部分
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    
    return i >= 0

使用示例

nums = [1, 2, 3]
print(nums)  # 输出: [1, 2, 3]

while next_permutation(nums):
    print(nums)
    
# 输出:
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 1, 2]
# [3, 2, 1]