[数据结构与算法]数组全排列 之 下一个排列，

排列组合问题

全排列之 从 “从小到大” 到 “从大到小”，like this

给你一个数组，求它在全排列队伍中的下一个状态

解题思路：

1、首先对数组状态进行勘探，是按从小到大排序的把状态记录下来，就是pair列表

2、pair列表里的最后一个列表所对应的nums里的两个位置的元素调换位置

pos=pair列表里的最后一个列表的第一个元素+1

3、从pos到nums的最后一个元素，按从小到大排序

#win7，python3.7.0-32

class Solution(object):					#面向对象编程，类，“object”可以没有
    def nextPermutation(self, nums):
        ls = len(nums)
        if ls <= 1:						#如果数组的长度小于1，就返回None
            return
        pair = []						#新建一个空列表，用来存储顺序对
        for i in range(ls):				#是从小到大的，位置都存入pair
            for j in range(i + 1, ls):
                if nums[i] < nums[j]:
                    pair.append([i,j])
        pos = 0							#pos=pair最后一个列表的第一个元素+1
        if len(pair) > 0:				#pos是nums里的位置
            self.swap(nums, pair[-1][0], pair[-1][1])#最后一对的两个元素调换位置
            pos = pair[-1][0] + 1
        for i in range(pos, ls):		#最后一对的第一个元素的位置开始
            for j in range(i + 1, ls):	#往后把大的放后面
                if nums[i] > nums[j]:
                    self.swap(nums, i, j)
        return nums
    def swap(self, nums, index1, index2):
        if index1 == index2:			 #节省算力，元素一样的就不用调换了
            return						#如果为了减少代码行数，这个if语句可以没有
        nums[index1], nums[index2] = nums[index2], nums[index1]
# %%
s = Solution()
print(s.nextPermutation(nums = []))
print(s.nextPermutation(nums = [1]))
print(s.nextPermutation(nums = [1,2,3,4]))
print(s.nextPermutation(nums = [1,2,4,3]))
print(s.nextPermutation(nums = [1,3,2,4]))
print(s.nextPermutation(nums = [1,3,4,2]))
print(s.nextPermutation(nums = [4,3,2,1]))
print(s.nextPermutation(nums = [1,2,3,3]))
print(s.nextPermutation([1,2,3,4,5]))
print(s.nextPermutation([1,2,3,5,4]))
print(s.nextPermutation([1,2,4,3,5]))
print(s.nextPermutation([1,2,4,5,3]))
print(s.nextPermutation([1,2,5,3,4]))
print(s.nextPermutation([1,2,5,4,3]))
print(s.nextPermutation([2,4,3,1]))

运行无故障，欢迎留言探讨。