[数据结构][Python][经典题目]寻找全排列下一个数

矫情吗；* 2023-10-11 10:30 4阅读 0赞

## 题目： ##

给出一个正整数，找出这个正整数的所有数字全排列的下一个数

## 思路： ##

以12345为例，为了和原数接近，需要尽量保持高位不变，低位在最小的范围内变换顺序。至于变换的范围大小取决于当前整数的逆序列区域。

如上图所示，12354的逆序区域是最后两位，仅看这两位已经是最大的组合。若要最接近原数，又比原数大，必须从第三位开始改变。  
12345的倒数第3位是3我们需要从后面的逆序区域找到大于3的最下数字，让其和3的位置互换。

互换之后的临时结果是12453，倒数第三位已经确定，这个时候最后两位仍是逆序态。我们需要转换成顺序态，以此保证在倒数第三位数值为4的情景下，后两位尽可能小。

## 综上，分析可知获取全排列下一个数的3个步骤。 ##

1.从后前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界。  
2.让逆序区域的前一位和逆序区域的中大于他的最小数字交互位置  
3.把原来的逆序区域转为顺序状态。

## 代码实现 ##

def findTransferPoint(numbers):
        for i in range(len(numbers)-1,-1,-1):
            if numbers[i]>numbers[i-1]:
                return i
        return 0
    
    def exchangeHead(numbers,index):
        head = numbers[index-1]
        for i in range(len(numbers)-1,-1,-1):
            if head<numbers[i]:
                numbers[index-1]=numbers[i]
                numbers[i]=head
                break;
        return numbers
    
    def num_reverse(numbers,index):
        for i in range(index,len(numbers)-1):
            for j in range(len(numbers)-1,-1,-1):
                if i<j:
                    temp = numbers[i]
                    numbers[i] = numbers[j]
                    numbers[j] = temp
        return numbers
    
    def main(numbers):
        index = findTransferPoint(numbers)
        if index == 0:
            return None
        exchangeHead(numbers,index)
        num_reverse(numbers,index)
        return numbers
    
    if __name__ == '__main__':
        res = main([1,2,5,3,4])
        print(res)

![在这里插入图片描述][20190922234552878.png]

[20190922234552878.png]: https://img-blog.csdnimg.cn/20190922234552878.png