前两天在一个算法交流群里有人贴出一道题下一个排列。他一开始直接用递归把全排列全部生成排序后查找当前位置再取下一条。小数据跑得通数据稍微大一点就直接超时。群里有人提醒他有标准解法核心三句话就能写完。但等到有人追问为什么从右往左找升序对为什么交换后要反转帮他的那个人也说不清楚了。这个场景我见过太多次。下一个排列是高频算法题但它不是那种背下模板就能应付的题目而是一个能延伸到全排列枚举、康托展开、状态压缩遍历的枢纽型考点。它表面考的是数组操作底层考的是你对字典序的理解。今天这篇文章不打算只贴一份标准代码而是把这道题从错误思路、数学原理、手工推导到边界条件、扩展应用完整走一遍。无论你是刚开始刷题的新手还是准备面试的在职开发者只要顺着逻辑推一遍后面遇到任何和排列顺序有关的问题都能自己推理出答案。1. 下一个排列的三条歪路暴力枚举、数字加一和直觉式改数先来说说我见过的三类错误解法。这三类错误代表三种不同的思维误区也解释了为什么这道题值得认真对待。1.1 暴力枚举看起来万无一失实际上n稍大就崩最直接的想法是把当前数字能组成的所有排列都生成出来按字典序排好找到当前排列然后取下一个。这个方案正确性没问题但复杂度是O(n!)n一旦大起来就是一场灾难。简单算一笔账n等于10时全排列是360多万个内存勉强还能扛住n等于12直接逼近4.8亿个排列n等于15排列总数超过一万亿。在这种量级下生成所有排列再查找任何在线评判系统都不会给你通过的机会。更不用说递归生成全排列时还要维护路径、处理去重、拷贝数组代码复杂度一点也不低。一个正确但几乎不可用的方案在算法题里就是零分方案。1.2 把排列当数字加一方向错了加得再多也不是排列第二类错解比较有迷惑性因为它利用了字典序和整数大小比较的相似性。有人把数组[1,2,3]看成整数123加一得到124再拆成[1,2,4]认为这就是答案。问题立刻就来了排列要求数字来自给定的集合且不重复124根本不是一个合法排列。再举一个例子[1,3,2]如果按数字加一变成134拆开后得到的[1,3,4]不仅超出了集合还直接跳过了正确答案[2,1,3]。这是因为排列的字典序虽然有逐位比较的特征但它没有十进制那种固定进位规则不能用数值加法模拟。把字典序当成普通整数运算是典型的看着像就往上套。1.3 从最左边改不知道下一个到底藏在右边哪里第三类错误藏在标准解法附近。有些人看完题解后会习惯性从数组左边开始找该改的数字。比如面对[1,5,8,4,7,6,5,3,1]心想1已经是最小开头了那就把第二位5换大一点变成[1,8,?, ?, ...]结果直接从[1,5]开头跳到了[1,8]开头中间以[1,5]为前缀的所有排列全部被跳过。字典序下的下一个要求严格意义上的相邻意味着只要后缀还有继续变大的空间前面任何一位都不能动。只有整个后缀已经大到不能再大时才轮到前一位做最小幅度的调整。所以答案一定藏在最靠右的还有增长空间的位置附近而不是左边某个数值较大的元素。这三条歪路有一个共同的病灶大家都在急着找某个更大的数却忽略了对下一个这个词语的精确理解。先把这个问题想清楚后面的三步算法就不是需要死记硬背的口诀而是顺理成章的推导结果。2. 字典序的底层规律为什么答案永远藏在最右侧的升级点2.1 字典序和数字比较是同一套直觉要理解下一个排列先必须理解排列之间的字典序关系。你可以把它想象成查英语词典的顺序先比较第一个字母相同再比较第二个还相同就继续往后。比如apple和apply前四个字母相同第五个字母e小于y所以apple排在apply前面。数组的字典序完全一样从索引0开始逐位比较遇到第一个不同的位置数值小的排列排前面。这种比较规则和多位整数的大小比较很像但有一个关键区别整数的不同位权重不同而字典序里所有位在决定顺序时没有权重差异——高位永远优先。正因为高位优先想让一个排列变成紧挨着的下一个最核心的原则就是尽量保持高位不动只在最靠右的位置做最小幅度的调整。这个尽量靠右动刀的原则几乎可以解释后面每一步算法的含义。2.2 后缀降序区一个排列的增长潜力已经耗尽看一个排列当前的状态你会发现它由两部分组成一个前缀和一个后缀。如果从某个位置开始后面的元素严格递减比如[7,6,5,3,1]那么这段后缀已经是它所能形成的最大字典序片段没有继续增大的空间了。以[1,5,8,4,7,6,5,3,1]为例从索引4开始的[7,6,5,3,1]是降序区这意味着以[1,5,8,4]作为前缀时后面的排列已经排到了最大形态。这时候你想让整个排列变大就不可能只在后缀内部做文章必须侵入后缀前面的那个元素也就是索引3位置的4。这个4就是整个排列增长的闸门。这就是为什么算法第一步要从右往左找第一个满足a[i] a[i1]的位置。倒过来扫描时遇到的第一前面比后面小的地方就是最靠右的、依然有增长潜力的位置。2.3 从右向左找第一个升序对到底在找什么很多题解只说找第一个升序对但没说为什么要从右往左找也没说这个升序对代表什么。本质原因是我们想从排列的最末端开始尽可能晚地扰动前缀。假设整个序列已经完全降序比如[3,2,1]任何位置的元素都比右边大找不到升序对说明这个排列已经是该数字集合下字典序最大的排列没有下一个只能整体反转回[1,2,3]。只要还存在升序对排列就还没走到尽头。最靠右的那个升序对决定了我们需要把哪一位当作升级点。你可以把a[i]理解成这次要进位的那一位它右边的所有元素都是降序说明以它为前缀时后面已经达到最大现在要做的事情是把a[i]换成比它大一点点的某个元素然后把右边恢复成最小排列也就是升序两者拼接起来就得到紧挨着的下一档。2.4 一次交换 一次反转为何恰好构成紧挨着的下一个找到升级点之后有两件事要做。第一用谁换掉a[i]为了不跳跃必须选择右侧降序区里比a[i]大的最小元素。从右往左扫描右侧降序区遇到的第一个大于a[i]的元素正好是这个刚大一点点的值因为区间降序越靠右的元素数值越小第一个大于a[i]的值就意味着大于a[i]的所有候选里最靠近a[i]的那一个。把这样一个元素换到a[i]的位置前缀得到的新值在数值上没有中间夹着其他可用数字因此不会跳过任何排列。第二换完之后怎么处理右边交换之后右侧区域不再是降序但还保留着一定的单调性把它整个反转就能得到该区域内字典序最小的排列。前缀刚好升了一小档后缀取最小值合在一起就是大于原排列的所有排列中最小的那一个。这就是下一个排列的精确含义。整个算法只需要一次扫描、一次交换、一次反转不需要排序就是因为寻找最小的大于a[i]和逆序成最小后缀两个动作合在一起恰好完成了精确进位的全部工作。3. 手工推导实录拿[1,5,8,4,7,6,5,3,1]完整走完三个步骤理论讲得再多不如动手走一遍。我选一个足够复杂的例子[1,5,8,4,7,6,5,3,1]。你跟着走一遍之后会发现代码只是这个过程的自然翻译。3.1 第一步锁定i3当前排列已经走到4开头的最后一档从数组最右边开始逐对向前比较比较a[8]1和a[7]3左边小于右边吗1 3不是我们要找的是从左往右看满足a[i] a[i1]的位置从右往左开始检查时当前位置i7的a[7]3a[8]13 1不成立继续。比较a[7]3和a[6]53 5不成立继续。比较a[6]5和a[5]65 6不成立继续。比较a[5]6和a[4]76 7不成立继续。比较a[4]7和a[3]44 7成立停。所以i3a[i]4。从i14开始后缀[7,6,5,3,1]严格降序。这个状态的含义是以[1,5,8,4]作为前四位时第五位之后的排列已经走到了最大形态[7,6,5,3,1]无法再往后走了。想继续变大只能把第四位的4进位。3.2 第二步从右侧降区里挑出刚好比4大一点的5右侧区间是[7,6,5,3,1]现在要找一个元素替换a[3]4。如果选择7新前缀从[1,5,8,4]跳到[1,5,8,7]跨度太大会跳过很多中间排列。选择3或1会让前缀变小违背下一个必须大于原排列的基本要求。正确做法是选择比4大的最小元素。从右往左扫描右侧区间1不大于43不大于45大于4停。找到j6a[j]5。这个5就是降序区里最靠右的、大于4的最小值。所有大于4的候选是5、6、7选5是唯一正确选项。3.3 第三步交换并反转得到[1,5,8,5,1,3,4,6,7]先交换a[3]和a[6]数组变成[1,5,8,5,7,6,4,3,1]。注意原本的4被放到了索引6的位置右侧从索引4开始是[7,6,4,3,1]仍然保持降序。接着从索引4到末尾整体反转[7,6,4,3,1]变成[1,3,4,6,7]。最终结果是[1,5,8,5,1,3,4,6,7]。这里有一个容易出错的细节反转的区间必须是从i1到末尾的整个子数组不是只反转局部。很多人漏掉从i1开始这个边界把升级点本身也反转进去导致结果完全错误。3.4 细节校验为什么交换后右侧依然是降序这个细节值得单独说。右侧区间[7,6,5,3,1]原本严格降序我们选中j6处的5与a[3]4交换后右侧变成了[7,6,4,3,1]依旧是降序。这不是巧合背后有两条数学保证。第一所有位于j左侧的值7、6都大于5也一定大于4所以它们依然大于新填入的4。第二所有位于j右侧的值3、1都不大于4——这里要用到5是右侧第一个大于4的值这个条件如果j右侧存在某个大于4的值按照降序排列它一定小于5从右往左扫描时就会先遇到它j就不会停在5。既然不存在这样的值j右侧所有元素都小于等于4新填入的4不会破坏降序。因此交换后右侧保持降序反转后便得到了严格升序的最小后缀。正是因为有这层数学保障算法才能一次反转收工而不是交换后还得排序。4. 代码落地最短实现、三种语言的差别、三个边界条件原理走通之后代码只有十几行。下面是不依赖任何语言库函数的手写实现以C为主附上Python对照。4.1 C实现与思路对照void nextPermutation(vectorint nums) { int n nums.size(); int i n - 2; while (i 0 nums[i] nums[i 1]) --i; if (i 0) { int j n - 1; while (j i nums[j] nums[i]) --j; swap(nums[i], nums[j]); } reverse(nums.begin() i 1, nums.end()); }代码很短但有两个比较符号值得反复琢磨。第一个是第一步循环里的nums[i] nums[i 1]它的作用是跳过所有已经降序的位置。只有写成才能保证最后停下来的i满足严格小于右边的条件如果写成遇到重复元素时会提前停在相等的位置逻辑直接错乱。第二个是第二步循环里的nums[j] nums[i]。右侧区间可能有等于nums[i]的值我们要找的是严格大于a[i]的最靠右元素所以必须用跳过所有等于目标值的位置。这一步错一个符号结果就是另一段完全不同的排列。如果第一步结束时i 0说明整个序列从头到尾都是降序已经是字典序最大的排列跳过交换直接整体反转就回到了字典序最小的排列。这份代码天然覆盖了这个情况因为此时reverse(nums.begin() 0, nums.end())就是对整个数组反转。4.2 Python版本def next_permutation(nums): n len(nums) i n - 2 while i 0 and nums[i] nums[i 1]: i - 1 if i 0: j n - 1 while nums[j] nums[i]: j - 1 nums[i], nums[j] nums[j], nums[i] nums[i 1:] reversed(nums[i 1:])Python的切片反转一行完成整体更短。注意reversed返回迭代器但切片赋值能正确处理。4.3 边界一长度小于2和纯降序序列长度是0或1时第一步循环根本不会进入反转一个空区间或单元素区间等于什么都没做所以不需要单独加判断。纯降序序列比如[3,2,1]第一步一路跳过直到i -1然后整个反转成[1,2,3]正好满足不存在下一个时返回最小排列的要求。这种接口设计有一个好处每次调用都得到字典序轮转中的下一个状态循环调用可以覆盖全部排列。4.4 边界二重复元素下找j时用还是重复元素是最容易写错的地方。来看一个具体的反例[3,1,2,1,1]。从右往左找升序对a[4]1和a[3]1相等跳过a[2]2和a[3]12 1不成立跳过a[1]1和a[2]21 2成立停。于是i1a[i]1右侧区间是[2,1,1]。现在从右往左找大于1的最小元素。用正确的写法j从末尾开始nums[4]11 1成立跳过nums[3]11 1成立跳过nums[2]22 1不成立停j2找到第二个位置的2正确。但如果把条件误写成nums[j] nums[i]j从末尾开始nums[4]11 1为假直接停j4选中的是一个等于a[i]的值整个算法立刻失效。所以在重复元素存在时和不是风格偏好而是正确性的前提。4.5 关于二分优化能用但没必要第二步在右侧降序区找大于a[i]的最小值因为区间单调递减理论上可以用二分把第二次扫描从O(n)降到O(logn)。但第一步找i本身就需要O(n)整体复杂度依然是O(n)空间复杂度O(1)。二分只能在常数上做一点优化不会改变数量级。在实际刷题和绝大多数业务场景中线性扫描就够了而且二分需要自定义比较函数处理重复元素时边界条件更容易出错性价比很低。5. 跳出一题看一类全排列枚举与康托展开下一个排列这个算法的价值远不止解决一道题。它最大的意义在于把全排列枚举从递归回溯路径记录简化成了循环状态变换。5.1 用next_permutation循环不用递归也能枚举全排列先对数组排序得到最小排列然后持续调用下一个排列直到回到最小排列为止vectorvectorint permute(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint res; do { res.push_back(nums); } while (next_permutation(nums.begin(), nums.end())); return res; }这个写法有很明显的优势。没有递归深度问题不会爆栈天然去重重复元素也只会枚举一次代码量远小于回溯版本。底层实现无论标准库怎么写核心语义都和我们前面推导的从右往左找升序对一致。如果你在面试中被要求手写完全可以自己实现一个替代。5.2 给定排列求序号康托展开的公式与例子知道一个排列在字典序中是第几个是康托展开解决的问题。设排列为p[0..n-1]对于每个位置i统计p[i]右侧有多少个比它小的数字记为cnt[i]则排名从1开始的计算公式是排名 1 Σ cnt[i] * (n-1-i)!举一个例子求排列[2,3,1]的排名i0值为2右侧比2小的只有1cnt 1i1值为3右侧比3小的只有1cnt 1i2值为1右侧比1小的没有cnt 0。代入公式1 1×2! 1×1! 0×0! 1 2 1 4。验证一下前4个排列是[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1][2,3,1]正好排第4。康托展开和下一个排列实际上是互逆关系一个是从排列到序号的映射另一个是序号附近的状态迁移。5.3 已知序号还原排列逆康托展开的思路反过来给一个排名r要求还原排列。先把r减去1然后不断用阶乘分解余数。举个例子r4n3r-133除以2!得到1余数1从剩余数字{1,2,3}中取第2小也就是21除以1!得到1余数0从剩余{1,3}中取第2小也就是30除以0!得到0从剩余{1}中取第1小也就是1。得到[2,3,1]和前面的例子对上了。逆康托展开的价值在于你可以直接跳到任意排名对应的排列而不必从最小排列一个个递推。这两道题放在一起理解才算真正摸到了排列序号的底层。5.4 重复元素时依然可以套用带重复元素的场景下康托展开需要调整统计方式统计比当前值小的数字时每个数字只计数一次并且要考虑剩余位置中重复元素的阶乘公式会复杂不少。不过实际工程和大多数算法题中直接调用next_permutation就能规避手工公式的复杂度因为标准库实现已经处理了重复元素。只有在需要精确排名或随机访问第k个排列时才需要认真实现去重版本的康托展开与逆展开。6. 面试追问、工程落地和我踩过的几个坑最后聊聊实战层面。这道题不是背下代码就能过关的面试官只要多追问两层很多人就会露馅。6.1 面试官最想听你讲清楚的两个点其实都是推导过程第一个点是为什么从右往左找第一个升序对。标准回答不是背诵步骤而是说清楚右侧的降序区已经达到了该前缀下的最大排列想要得到紧邻的下一个排列必须在尽可能靠右的位置做一次进位。第二个点是为什么选择比a[i]大的最小元素。因为这样能保证改动后的前缀比原来大且是所有可能前缀里增幅最小的后缀再逆序成最小整体才不会跳过任何中间排列。能把这两点当场推出来比默写代码更能让面试官认可。6.2 写码时最容易翻车的三件事翻车第一件把第一步的写成。在重复元素数组里等于没有被跳过循环可能一路走到底导致本不该整体反转的排列被整体反转。翻车第二件找到i之后忘记反转右侧或者反转范围写错。比如[1,3,2]的标准答案是[2,1,3]如果只交换不反转会得到[2,3,1]它虽然比原排列大但跳过了[2,1,3]这中间一个排列。翻车第三件C里使用std::reverse时迭代器范围出错把nums.begin() i 1写成nums.begin() i把升级点本身也反转进去。解决这些问题的可靠方法是找一个固定测试数组在本地把全排列序列全部打印出来对着字典序表逐一检查结果而不是只凭眼睛看某一个中间状态。6.3 工程中的真实使用场景从SKU组合到状态枚举很多入门者以为下一个排列只活在面试题里其实业务中也有它的身影。我在一个模拟项目X里处理过订单SKU的规格组合需要按特定优先级遍历所有组合如果每次都用递归生成排列数据量一上来递归深度和重复状态都会失控。改用排序next_permutation的循环方案后状态稳定还能随时从任意中间状态续跑。类似的场景还有权限组合枚举、测试用例的排列覆盖以及一些需要按字典序递进生成状态的算法框架。它的核心价值不是一次性生成所有排列而是提供一个无状态、可暂停、可续跑的顺序生成器。6.4 我踩过的一次二分优化翻车经历有一段时间我总觉得线性扫描不够优雅非要把第二步改成二分。右侧区间是降序我写了一个自定义比较的upper_bound普通测试全部通过一上[3,1,2,1,1]这种带重复元素的用例就错。排查了半天发现是二分的边界条件没有处理好严格大于和相等元素跳过的优先级最后把代码改回从右往左的线性扫描一行while干净利落地解决。那次之后我的体会是不要为了优化而优化。特别是当优化只能降低常数、不能改变复杂度量级时正确性和可读性永远排在前面。这道题我已经写过很多遍现在每次用到它时心里默念的就是三句话找最右的升序对换右边最接近的大数反转后缀。只要这三句话的逻辑链条还在任何语言、任何边界情况都不会让我发怵。排列问题的核心就是理解字典序的进位规则理解了它下一个排列就不再是题库里的一道题而是一把随手可用的钥匙。 
长河君 · 2026/10/14 7:25:54 · 阅读 1.2k 下一个排列算法：字典序原理、全排列枚举与工程应用
前两天在一个算法交流群里有人贴出一道题下一个排列。他一开始直接用递归把全排列全部生成排序后查找当前位置再取下一条。小数据跑得通数据稍微大一点就直接超时。群里有人提醒他有标准解法核心三句话就能写完。但等到有人追问为什么从右往左找升序对为什么交换后要反转帮他的那个人也说不清楚了。这个场景我见过太多次。下一个排列是高频算法题但它不是那种背下模板就能应付的题目而是一个能延伸到全排列枚举、康托展开、状态压缩遍历的枢纽型考点。它表面考的是数组操作底层考的是你对字典序的理解。今天这篇文章不打算只贴一份标准代码而是把这道题从错误思路、数学原理、手工推导到边界条件、扩展应用完整走一遍。无论你是刚开始刷题的新手还是准备面试的在职开发者只要顺着逻辑推一遍后面遇到任何和排列顺序有关的问题都能自己推理出答案。1. 下一个排列的三条歪路暴力枚举、数字加一和直觉式改数先来说说我见过的三类错误解法。这三类错误代表三种不同的思维误区也解释了为什么这道题值得认真对待。1.1 暴力枚举看起来万无一失实际上n稍大就崩最直接的想法是把当前数字能组成的所有排列都生成出来按字典序排好找到当前排列然后取下一个。这个方案正确性没问题但复杂度是O(n!)n一旦大起来就是一场灾难。简单算一笔账n等于10时全排列是360多万个内存勉强还能扛住n等于12直接逼近4.8亿个排列n等于15排列总数超过一万亿。在这种量级下生成所有排列再查找任何在线评判系统都不会给你通过的机会。更不用说递归生成全排列时还要维护路径、处理去重、拷贝数组代码复杂度一点也不低。一个正确但几乎不可用的方案在算法题里就是零分方案。1.2 把排列当数字加一方向错了加得再多也不是排列第二类错解比较有迷惑性因为它利用了字典序和整数大小比较的相似性。有人把数组[1,2,3]看成整数123加一得到124再拆成[1,2,4]认为这就是答案。问题立刻就来了排列要求数字来自给定的集合且不重复124根本不是一个合法排列。再举一个例子[1,3,2]如果按数字加一变成134拆开后得到的[1,3,4]不仅超出了集合还直接跳过了正确答案[2,1,3]。这是因为排列的字典序虽然有逐位比较的特征但它没有十进制那种固定进位规则不能用数值加法模拟。把字典序当成普通整数运算是典型的看着像就往上套。1.3 从最左边改不知道下一个到底藏在右边哪里第三类错误藏在标准解法附近。有些人看完题解后会习惯性从数组左边开始找该改的数字。比如面对[1,5,8,4,7,6,5,3,1]心想1已经是最小开头了那就把第二位5换大一点变成[1,8,?, ?, ...]结果直接从[1,5]开头跳到了[1,8]开头中间以[1,5]为前缀的所有排列全部被跳过。字典序下的下一个要求严格意义上的相邻意味着只要后缀还有继续变大的空间前面任何一位都不能动。只有整个后缀已经大到不能再大时才轮到前一位做最小幅度的调整。所以答案一定藏在最靠右的还有增长空间的位置附近而不是左边某个数值较大的元素。这三条歪路有一个共同的病灶大家都在急着找某个更大的数却忽略了对下一个这个词语的精确理解。先把这个问题想清楚后面的三步算法就不是需要死记硬背的口诀而是顺理成章的推导结果。2. 字典序的底层规律为什么答案永远藏在最右侧的升级点2.1 字典序和数字比较是同一套直觉要理解下一个排列先必须理解排列之间的字典序关系。你可以把它想象成查英语词典的顺序先比较第一个字母相同再比较第二个还相同就继续往后。比如apple和apply前四个字母相同第五个字母e小于y所以apple排在apply前面。数组的字典序完全一样从索引0开始逐位比较遇到第一个不同的位置数值小的排列排前面。这种比较规则和多位整数的大小比较很像但有一个关键区别整数的不同位权重不同而字典序里所有位在决定顺序时没有权重差异——高位永远优先。正因为高位优先想让一个排列变成紧挨着的下一个最核心的原则就是尽量保持高位不动只在最靠右的位置做最小幅度的调整。这个尽量靠右动刀的原则几乎可以解释后面每一步算法的含义。2.2 后缀降序区一个排列的增长潜力已经耗尽看一个排列当前的状态你会发现它由两部分组成一个前缀和一个后缀。如果从某个位置开始后面的元素严格递减比如[7,6,5,3,1]那么这段后缀已经是它所能形成的最大字典序片段没有继续增大的空间了。以[1,5,8,4,7,6,5,3,1]为例从索引4开始的[7,6,5,3,1]是降序区这意味着以[1,5,8,4]作为前缀时后面的排列已经排到了最大形态。这时候你想让整个排列变大就不可能只在后缀内部做文章必须侵入后缀前面的那个元素也就是索引3位置的4。这个4就是整个排列增长的闸门。这就是为什么算法第一步要从右往左找第一个满足a[i] a[i1]的位置。倒过来扫描时遇到的第一前面比后面小的地方就是最靠右的、依然有增长潜力的位置。2.3 从右向左找第一个升序对到底在找什么很多题解只说找第一个升序对但没说为什么要从右往左找也没说这个升序对代表什么。本质原因是我们想从排列的最末端开始尽可能晚地扰动前缀。假设整个序列已经完全降序比如[3,2,1]任何位置的元素都比右边大找不到升序对说明这个排列已经是该数字集合下字典序最大的排列没有下一个只能整体反转回[1,2,3]。只要还存在升序对排列就还没走到尽头。最靠右的那个升序对决定了我们需要把哪一位当作升级点。你可以把a[i]理解成这次要进位的那一位它右边的所有元素都是降序说明以它为前缀时后面已经达到最大现在要做的事情是把a[i]换成比它大一点点的某个元素然后把右边恢复成最小排列也就是升序两者拼接起来就得到紧挨着的下一档。2.4 一次交换 一次反转为何恰好构成紧挨着的下一个找到升级点之后有两件事要做。第一用谁换掉a[i]为了不跳跃必须选择右侧降序区里比a[i]大的最小元素。从右往左扫描右侧降序区遇到的第一个大于a[i]的元素正好是这个刚大一点点的值因为区间降序越靠右的元素数值越小第一个大于a[i]的值就意味着大于a[i]的所有候选里最靠近a[i]的那一个。把这样一个元素换到a[i]的位置前缀得到的新值在数值上没有中间夹着其他可用数字因此不会跳过任何排列。第二换完之后怎么处理右边交换之后右侧区域不再是降序但还保留着一定的单调性把它整个反转就能得到该区域内字典序最小的排列。前缀刚好升了一小档后缀取最小值合在一起就是大于原排列的所有排列中最小的那一个。这就是下一个排列的精确含义。整个算法只需要一次扫描、一次交换、一次反转不需要排序就是因为寻找最小的大于a[i]和逆序成最小后缀两个动作合在一起恰好完成了精确进位的全部工作。3. 手工推导实录拿[1,5,8,4,7,6,5,3,1]完整走完三个步骤理论讲得再多不如动手走一遍。我选一个足够复杂的例子[1,5,8,4,7,6,5,3,1]。你跟着走一遍之后会发现代码只是这个过程的自然翻译。3.1 第一步锁定i3当前排列已经走到4开头的最后一档从数组最右边开始逐对向前比较比较a[8]1和a[7]3左边小于右边吗1 3不是我们要找的是从左往右看满足a[i] a[i1]的位置从右往左开始检查时当前位置i7的a[7]3a[8]13 1不成立继续。比较a[7]3和a[6]53 5不成立继续。比较a[6]5和a[5]65 6不成立继续。比较a[5]6和a[4]76 7不成立继续。比较a[4]7和a[3]44 7成立停。所以i3a[i]4。从i14开始后缀[7,6,5,3,1]严格降序。这个状态的含义是以[1,5,8,4]作为前四位时第五位之后的排列已经走到了最大形态[7,6,5,3,1]无法再往后走了。想继续变大只能把第四位的4进位。3.2 第二步从右侧降区里挑出刚好比4大一点的5右侧区间是[7,6,5,3,1]现在要找一个元素替换a[3]4。如果选择7新前缀从[1,5,8,4]跳到[1,5,8,7]跨度太大会跳过很多中间排列。选择3或1会让前缀变小违背下一个必须大于原排列的基本要求。正确做法是选择比4大的最小元素。从右往左扫描右侧区间1不大于43不大于45大于4停。找到j6a[j]5。这个5就是降序区里最靠右的、大于4的最小值。所有大于4的候选是5、6、7选5是唯一正确选项。3.3 第三步交换并反转得到[1,5,8,5,1,3,4,6,7]先交换a[3]和a[6]数组变成[1,5,8,5,7,6,4,3,1]。注意原本的4被放到了索引6的位置右侧从索引4开始是[7,6,4,3,1]仍然保持降序。接着从索引4到末尾整体反转[7,6,4,3,1]变成[1,3,4,6,7]。最终结果是[1,5,8,5,1,3,4,6,7]。这里有一个容易出错的细节反转的区间必须是从i1到末尾的整个子数组不是只反转局部。很多人漏掉从i1开始这个边界把升级点本身也反转进去导致结果完全错误。3.4 细节校验为什么交换后右侧依然是降序这个细节值得单独说。右侧区间[7,6,5,3,1]原本严格降序我们选中j6处的5与a[3]4交换后右侧变成了[7,6,4,3,1]依旧是降序。这不是巧合背后有两条数学保证。第一所有位于j左侧的值7、6都大于5也一定大于4所以它们依然大于新填入的4。第二所有位于j右侧的值3、1都不大于4——这里要用到5是右侧第一个大于4的值这个条件如果j右侧存在某个大于4的值按照降序排列它一定小于5从右往左扫描时就会先遇到它j就不会停在5。既然不存在这样的值j右侧所有元素都小于等于4新填入的4不会破坏降序。因此交换后右侧保持降序反转后便得到了严格升序的最小后缀。正是因为有这层数学保障算法才能一次反转收工而不是交换后还得排序。4. 代码落地最短实现、三种语言的差别、三个边界条件原理走通之后代码只有十几行。下面是不依赖任何语言库函数的手写实现以C为主附上Python对照。4.1 C实现与思路对照void nextPermutation(vectorint nums) { int n nums.size(); int i n - 2; while (i 0 nums[i] nums[i 1]) --i; if (i 0) { int j n - 1; while (j i nums[j] nums[i]) --j; swap(nums[i], nums[j]); } reverse(nums.begin() i 1, nums.end()); }代码很短但有两个比较符号值得反复琢磨。第一个是第一步循环里的nums[i] nums[i 1]它的作用是跳过所有已经降序的位置。只有写成才能保证最后停下来的i满足严格小于右边的条件如果写成遇到重复元素时会提前停在相等的位置逻辑直接错乱。第二个是第二步循环里的nums[j] nums[i]。右侧区间可能有等于nums[i]的值我们要找的是严格大于a[i]的最靠右元素所以必须用跳过所有等于目标值的位置。这一步错一个符号结果就是另一段完全不同的排列。如果第一步结束时i 0说明整个序列从头到尾都是降序已经是字典序最大的排列跳过交换直接整体反转就回到了字典序最小的排列。这份代码天然覆盖了这个情况因为此时reverse(nums.begin() 0, nums.end())就是对整个数组反转。4.2 Python版本def next_permutation(nums): n len(nums) i n - 2 while i 0 and nums[i] nums[i 1]: i - 1 if i 0: j n - 1 while nums[j] nums[i]: j - 1 nums[i], nums[j] nums[j], nums[i] nums[i 1:] reversed(nums[i 1:])Python的切片反转一行完成整体更短。注意reversed返回迭代器但切片赋值能正确处理。4.3 边界一长度小于2和纯降序序列长度是0或1时第一步循环根本不会进入反转一个空区间或单元素区间等于什么都没做所以不需要单独加判断。纯降序序列比如[3,2,1]第一步一路跳过直到i -1然后整个反转成[1,2,3]正好满足不存在下一个时返回最小排列的要求。这种接口设计有一个好处每次调用都得到字典序轮转中的下一个状态循环调用可以覆盖全部排列。4.4 边界二重复元素下找j时用还是重复元素是最容易写错的地方。来看一个具体的反例[3,1,2,1,1]。从右往左找升序对a[4]1和a[3]1相等跳过a[2]2和a[3]12 1不成立跳过a[1]1和a[2]21 2成立停。于是i1a[i]1右侧区间是[2,1,1]。现在从右往左找大于1的最小元素。用正确的写法j从末尾开始nums[4]11 1成立跳过nums[3]11 1成立跳过nums[2]22 1不成立停j2找到第二个位置的2正确。但如果把条件误写成nums[j] nums[i]j从末尾开始nums[4]11 1为假直接停j4选中的是一个等于a[i]的值整个算法立刻失效。所以在重复元素存在时和不是风格偏好而是正确性的前提。4.5 关于二分优化能用但没必要第二步在右侧降序区找大于a[i]的最小值因为区间单调递减理论上可以用二分把第二次扫描从O(n)降到O(logn)。但第一步找i本身就需要O(n)整体复杂度依然是O(n)空间复杂度O(1)。二分只能在常数上做一点优化不会改变数量级。在实际刷题和绝大多数业务场景中线性扫描就够了而且二分需要自定义比较函数处理重复元素时边界条件更容易出错性价比很低。5. 跳出一题看一类全排列枚举与康托展开下一个排列这个算法的价值远不止解决一道题。它最大的意义在于把全排列枚举从递归回溯路径记录简化成了循环状态变换。5.1 用next_permutation循环不用递归也能枚举全排列先对数组排序得到最小排列然后持续调用下一个排列直到回到最小排列为止vectorvectorint permute(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint res; do { res.push_back(nums); } while (next_permutation(nums.begin(), nums.end())); return res; }这个写法有很明显的优势。没有递归深度问题不会爆栈天然去重重复元素也只会枚举一次代码量远小于回溯版本。底层实现无论标准库怎么写核心语义都和我们前面推导的从右往左找升序对一致。如果你在面试中被要求手写完全可以自己实现一个替代。5.2 给定排列求序号康托展开的公式与例子知道一个排列在字典序中是第几个是康托展开解决的问题。设排列为p[0..n-1]对于每个位置i统计p[i]右侧有多少个比它小的数字记为cnt[i]则排名从1开始的计算公式是排名 1 Σ cnt[i] * (n-1-i)!举一个例子求排列[2,3,1]的排名i0值为2右侧比2小的只有1cnt 1i1值为3右侧比3小的只有1cnt 1i2值为1右侧比1小的没有cnt 0。代入公式1 1×2! 1×1! 0×0! 1 2 1 4。验证一下前4个排列是[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1][2,3,1]正好排第4。康托展开和下一个排列实际上是互逆关系一个是从排列到序号的映射另一个是序号附近的状态迁移。5.3 已知序号还原排列逆康托展开的思路反过来给一个排名r要求还原排列。先把r减去1然后不断用阶乘分解余数。举个例子r4n3r-133除以2!得到1余数1从剩余数字{1,2,3}中取第2小也就是21除以1!得到1余数0从剩余{1,3}中取第2小也就是30除以0!得到0从剩余{1}中取第1小也就是1。得到[2,3,1]和前面的例子对上了。逆康托展开的价值在于你可以直接跳到任意排名对应的排列而不必从最小排列一个个递推。这两道题放在一起理解才算真正摸到了排列序号的底层。5.4 重复元素时依然可以套用带重复元素的场景下康托展开需要调整统计方式统计比当前值小的数字时每个数字只计数一次并且要考虑剩余位置中重复元素的阶乘公式会复杂不少。不过实际工程和大多数算法题中直接调用next_permutation就能规避手工公式的复杂度因为标准库实现已经处理了重复元素。只有在需要精确排名或随机访问第k个排列时才需要认真实现去重版本的康托展开与逆展开。6. 面试追问、工程落地和我踩过的几个坑最后聊聊实战层面。这道题不是背下代码就能过关的面试官只要多追问两层很多人就会露馅。6.1 面试官最想听你讲清楚的两个点其实都是推导过程第一个点是为什么从右往左找第一个升序对。标准回答不是背诵步骤而是说清楚右侧的降序区已经达到了该前缀下的最大排列想要得到紧邻的下一个排列必须在尽可能靠右的位置做一次进位。第二个点是为什么选择比a[i]大的最小元素。因为这样能保证改动后的前缀比原来大且是所有可能前缀里增幅最小的后缀再逆序成最小整体才不会跳过任何中间排列。能把这两点当场推出来比默写代码更能让面试官认可。6.2 写码时最容易翻车的三件事翻车第一件把第一步的写成。在重复元素数组里等于没有被跳过循环可能一路走到底导致本不该整体反转的排列被整体反转。翻车第二件找到i之后忘记反转右侧或者反转范围写错。比如[1,3,2]的标准答案是[2,1,3]如果只交换不反转会得到[2,3,1]它虽然比原排列大但跳过了[2,1,3]这中间一个排列。翻车第三件C里使用std::reverse时迭代器范围出错把nums.begin() i 1写成nums.begin() i把升级点本身也反转进去。解决这些问题的可靠方法是找一个固定测试数组在本地把全排列序列全部打印出来对着字典序表逐一检查结果而不是只凭眼睛看某一个中间状态。6.3 工程中的真实使用场景从SKU组合到状态枚举很多入门者以为下一个排列只活在面试题里其实业务中也有它的身影。我在一个模拟项目X里处理过订单SKU的规格组合需要按特定优先级遍历所有组合如果每次都用递归生成排列数据量一上来递归深度和重复状态都会失控。改用排序next_permutation的循环方案后状态稳定还能随时从任意中间状态续跑。类似的场景还有权限组合枚举、测试用例的排列覆盖以及一些需要按字典序递进生成状态的算法框架。它的核心价值不是一次性生成所有排列而是提供一个无状态、可暂停、可续跑的顺序生成器。6.4 我踩过的一次二分优化翻车经历有一段时间我总觉得线性扫描不够优雅非要把第二步改成二分。右侧区间是降序我写了一个自定义比较的upper_bound普通测试全部通过一上[3,1,2,1,1]这种带重复元素的用例就错。排查了半天发现是二分的边界条件没有处理好严格大于和相等元素跳过的优先级最后把代码改回从右往左的线性扫描一行while干净利落地解决。那次之后我的体会是不要为了优化而优化。特别是当优化只能降低常数、不能改变复杂度量级时正确性和可读性永远排在前面。这道题我已经写过很多遍现在每次用到它时心里默念的就是三句话找最右的升序对换右边最接近的大数反转后缀。只要这三句话的逻辑链条还在任何语言、任何边界情况都不会让我发怵。排列问题的核心就是理解字典序的进位规则理解了它下一个排列就不再是题库里的一道题而是一把随手可用的钥匙。