排列"/>

下一个（全）排列

目录

一、前言

二、下一个（全）排列

1、问题描述

2、基本分析

三、第一个题例

1、上链接

2、思路

3、python代码

四、第二个题例

1、上链接

2、思路

3、python代码

一、前言

对于学计算机的同学来说，学习算法是一件非常重要的事情，废话不多讲，我们来讲讲“下一个（全）排列问题”。

二、下一个（全）排列

1、问题描述

整数数组的一个 排列，就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 “下一个排列” 是指其整数的下一个字典序更大的排列。

更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。

如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

注：必须 “原地” 修改，只允许使用额外常数空间。

2、基本分析

（1）先倒序遍历数组，找到第一个 nums[i] (前一个数比后一个数小的位置) (即nums[i] < nums[i+1]);

（2）这个时候我们不能直接把后一个数nums[i+1] 跟前一个数nums[i]交换就完事了；还应该从“nums[i+1]-->数组末尾” 这一段的数据中找出最优的那个值 (如何最优? 即比nums[i]稍微大那么一丢丢的数，也就是 nums[i+1]-->数组末尾中，比nums[i]大的数中最小的那个值)

（3）找到之后，跟num[i]交换，这还不算是下一个排列，num[i]后面的数值还不够小，所以还应当进升序排列

举个例子：

nums = [1,2,7,4,3,1]

（1）第一步: 倒序遍历数组，找出第一组：前一个数比后一个数小的两个数，即[2, 7]

（2）2所处的这个位置就是需要找出比它稍微大的数的位置；

（3）我们从 [7,4,3,1] 中找出比2大的数中的最小值，也就是3，找到后跟2交换即可；当然了，如果没找到的话，直接跳到第5步，直接升序排列输出。

（4）目前nums=[1,3,7,4,2,1]，不用我说你们也看出来还不算下一个排列

（5）对3后面的数，升序排列，即最终结果: nums = [1,3,1,2,4,7]

三、第一个题例

1、上链接

31. 下一个排列 - 力扣（Leetcode）

2、思路

同上分析。

3、python代码

nums=list(map(int,input().split()))   # 输入一个nums数组n=len(nums)for i in range(n-2,-1,-1):if nums[i]<nums[i+1]:for j in range(n-1,i,-1):if nums[j]>nums[i]:nums[i],nums[j]=nums[j],nums[i]breaknums[i+1:]=sorted(nums[i+1:]) # sorted()不会改变原数组顺序breakelse:if i==0:nums.sort()  # sort()是会改变原数组顺序的print(nums)# 套力扣 python3 模板格式 (31. 下一个排列)
# 时间 48 ms，击败7.11%
# 内存 14.8 MB，击败91.19%
'''
class Solution:def nextPermutation(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""n=len(nums)for i in range(n-2,-1,-1):if nums[i]<nums[i+1]:for j in range(n-1,i,-1):if nums[j]>nums[i]:nums[i],nums[j]=nums[j],nums[i]breaknums[i+1:]=sorted(nums[i+1:]) # sorted()不会改变原数组顺序breakelse:if i==0:nums.sort()  # sort()是会改变原数组顺序的
'''

四、第二个题例

1、上链接

P1088 [NOIP2004 普及组] 火星人 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

2、思路

同上分析。

3、python代码

class Solution:def next_permulation(self,nums)->None:n=len(nums)for i in range(n-2,-1,-1):if nums[i]<nums[i+1]:for j in range(n-1,i,-1):if nums[j]>nums[i]:nums[i],nums[j]=nums[j],nums[i]breaknums[i+1:]=sorted(nums[i+1:]) # sorted()不会改变原数组顺序breakelse:if i==0:nums.sort()  # sort()是会改变原数组顺序的if __name__=='__main__':n=int(input())m=int(input())nums=list(map(int,input().split()))   # 输入一个nums数组for _ in range(m):Solution.next_permulation(Solution,nums)l=len(nums)for i in range(l-1):print(nums[i],end=" ")print(nums[l-1],end="")

以上，下一个（全）排列。

祝好