简介这份资源聚焦计算机科学中的经典问题——N个数全排列的非递归实现面向正在学习算法与数据结构、希望摆脱递归思维定式或规避栈溢出风险的编程学习者。资源以C源码形式呈现通过迭代与回溯思路完成排列生成可用于算法教学演示、数据处理工具开发或面试刷题参考。压缩包内共1个文件为cpp源代码文件整体仅879B体量轻巧便于直接阅读与移植。目前已有625人学习下载说明该实现具备一定的参考价值。读者可从中获取非递归全排列的核心代码框架理解初始化、循环遍历、元素交换、结果记录与回溯调整等关键环节并借鉴避免重复排列的标记思路。代码结构紧凑适合作为算法课程作业、竞赛模板或工程中排列枚举模块的起点也可在此基础上扩展为字典序输出或去重版本。1. 全排列非递归为什么递归写得好好的我还要把它拆掉写全排列这件事递归版本几乎是所有人的第一反应交换、递归、回溯三行核心代码就能跑。但真把它放进生产环境问题就来了。N 稍微大一点比如 N12递归深度直接顶到 12 层每层还要保存局部变量和返回地址N15 时栈帧开销开始明显拖慢速度如果跑在嵌入式设备或者对栈空间有硬限制的环境里递归版本甚至可能直接崩掉。更麻烦的是递归天然不适合做「下一个排列」这种增量式输出——你没法在任意时刻暂停、保存状态、下次接着跑。非递归全排列解决的正是这个问题用显式的状态变量替代函数调用栈把「生成下一个排列」变成一个可以随时中断、随时恢复的循环过程。它适合三类人一是需要在资源受限环境里跑排列枚举的嵌入式开发者二是要做排列流式输出、不想一次性算完的场景三是想真正理解字典序排列生成逻辑、而不是靠递归「黑匣子」蒙混过关的学习者。下面我从字典序算法讲到自实现栈模拟把参数、边界和踩坑点全部摊开。2. 字典序下一个排列非递归方案里最稳的一条路2.1 为什么字典序法是非递归的首选非递归生成全排列有好几种思路字典序法、递归转栈模拟、Johnson-Trotter 邻位交换法、堆算法Heaps algorithm的迭代版。这几种里我一般首推字典序法原因有三。第一它天然按从小到大输出结果有序方便做二分查找或者提前终止。第二它每次只做「找逆序对 → 交换 → 反转后缀」三步逻辑清晰没有隐藏状态。第三它不依赖任何额外数据结构空间复杂度 O(1)不算输出数组本身这在内存紧张的场合很关键。Johnson-Trotter 虽然每步只交换一对相邻元素理论交换次数最少但它需要维护每个元素的移动方向标记状态管理反而更绕。堆算法的迭代版交换次数也少但输出顺序是乱的不适合需要有序枚举的场景。所以综合来看字典序法是工程上最平衡的选择。2.2 字典序算法的三个核心步骤先把算法逻辑说清楚。给定一个排列要找到字典序意义下的「下一个更大排列」分三步从右往左找第一个升序对找到最大的索引 i使得 a[i] a[i1]。如果找不到说明当前已经是最大排列完全降序整个枚举结束。从右往左找第一个大于 a[i] 的元素找到最大的索引 j使得 a[j] a[i]。因为 a[i1..n-1] 是降序的所以从右往左第一个大于 a[i] 的就是我们要找的。交换 a[i] 和 a[j]然后反转 a[i1..n-1]交换后后缀仍然是降序反转它就变成升序得到恰好比原排列大的下一个排列。这三步的正确性来自字典序的定义要让排列变大必须从最靠右的位置开始调整找到最靠右的可增大位置 i用后缀中刚好比它大的元素替换再把后缀压到最小升序就得到了下一个排列。2.3 用 Python 跑通最小可复现版本下面是一个完整的 Python 实现包含排列生成和调用示例def next_permutation(a): 原地修改数组 a返回 True 表示还有下一个排列False 表示已到最大 n len(a) # 步骤1从右往左找第一个升序对 a[i] a[i1] i n - 2 while i 0 and a[i] a[i 1]: i - 1 if i 0: return False # 已经是完全降序没有下一个了 # 步骤2从右往左找第一个大于 a[i] 的元素 j n - 1 while a[j] a[i]: j - 1 # 步骤3交换 a[i] 和 a[j] a[i], a[j] a[j], a[i] # 步骤4反转 a[i1..n-1]使其变为升序 left, right i 1, n - 1 while left right: a[left], a[right] a[right], a[left] left 1 right - 1 return True def all_permutations(n): 生成 1..n 的全排列按字典序输出 a list(range(1, n 1)) results [a[:]] # 第一个排列 while next_permutation(a): results.append(a[:]) return results if __name__ __main__: perms all_permutations(4) for p in perms: print(p) print(f共 {len(perms)} 个排列)这段代码里next_permutation是核心它原地修改数组并返回布尔值。all_permutations先记录初始升序排列然后不断调用next_permutation直到返回 False。注意results.append(a[:])里的切片操作如果不切片直接 append(a)所有结果都会指向同一个列表对象最后全变成同一个排列——这是新手最容易翻车的地方。2.4 关键参数与边界条件参数/条件含义注意事项n 0空数组应直接返回空结果不要进入循环n 1单元素只有一个排列next_permutation 立即返回 False完全降序输入如 [3,2,1]算法应返回 False表示无下一个排列重复元素如 [1,1,2]字典序法天然去重输出不重复排列i 的初始值n-2从倒数第二个元素开始比较j 的查找条件a[j] a[i]严格大于不是大于等于重复元素这一点值得展开说。如果数组里有重复值字典序法仍然正确因为步骤 1 找的是严格升序对a[i] a[i1]步骤 2 找的是严格大于 a[i] 的元素等于的情况会被跳过。所以 [1,1,2] 只会生成 [1,1,2]、[1,2,1]、[2,1,1] 三个排列不会重复。这是字典序法相比交换法的一个明显优势——交换法需要额外用集合去重。3. 不用字典序也行用显式栈模拟递归过程3.1 什么时候该放弃字典序法字典序法虽好但它有一个前提你必须能定义「下一个排列」的偏序关系。如果题目要求的是按某种自定义顺序输出排列或者你需要在生成过程中做剪枝比如回溯类问题字典序法就不够灵活了。这时候更通用的做法是把递归过程用显式栈模拟出来。递归的本质是系统帮你维护了一个调用栈每个栈帧保存了当前处理到哪一层、循环变量走到哪、以及局部状态。非递归化就是自己用一个栈结构把这些信息存起来用一个循环驱动。3.2 显式栈模拟的通用模板以「依次为每个位置选择一个未使用的数」为例递归版本是这样的def permute_recursive(nums, path, used, result): if len(path) len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) permute_recursive(nums, path, used, result) path.pop() used[i] False把它改成显式栈版本核心是把「当前处理到第几个位置」和「这个位置下一个要尝试的候选索引」压入栈def permute_iterative(nums): n len(nums) result [] used [False] * n path [] # 栈中每个元素: (当前层索引, 下一个候选元素索引) stack [(0, 0)] while stack: depth, idx stack.pop() # 如果这一层已经选好了元素先回退状态 if depth len(path): # 回退把上一轮选的元素标记为未使用 removed path.pop() used[removed] False # 从 idx 开始找下一个可用元素 found False for i in range(idx, n): if not used[i]: used[i] True path.append(i) if len(path) n: result.append([nums[k] for k in path]) # 到达叶子回退 path.pop() used[i] False else: # 压入当前层的下一个候选再压入下一层 stack.append((depth, i 1)) stack.append((depth 1, 0)) found True break # 如果这一层没有更多候选自然结束栈中已无本层记录 return result这段代码比字典序版本复杂不少但它的优势在于通用性你可以在if len(path) n之前插入任意剪枝条件也可以在压栈时调整候选顺序来实现自定义枚举顺序。3.3 栈模拟版本的状态管理要点写显式栈版本时有三个状态必须同步维护used 数组标记哪些元素已经被选入当前路径。每次入栈选元素时置 True回退时置 False。path 列表当前路径。入栈时 append回退时 pop。栈帧中的 idx记录当前层下一次应该从哪个候选开始尝试避免重复枚举。最容易出错的地方是回退时机。在上面的实现里每次从栈中弹出一个(depth, idx)时如果depth len(path)说明这一层之前已经选过元素了需要先把那个元素回退掉。这个判断条件依赖 path 的长度和 depth 的关系写反了就会导致状态错乱。另一个坑是栈的压入顺序。因为栈是后进先出如果要先处理下一层必须先把「当前层的下一个候选」压入再把「下一层的起始帧」压入。顺序反了就会变成深度优先变成广度优先输出顺序完全不对。4. 避坑与排查非递归全排列最容易翻车的五个地方4.1 现象输出结果全部相同原因在把 path 加入 result 时没有做拷贝直接 append 了 path 的引用。后续 path 被修改result 里所有元素都跟着变。解决Python 里用result.append(path[:])或result.append(list(path))C 里用result.push_back(vectorint(path))Java 里用result.add(new ArrayList(path))。一句话存快照不存引用。4.2 现象字典序法漏掉了最后一个排列原因循环条件写成了while next_permutation(a):然后在循环体里收集但初始排列没有单独收集。最后一个排列是在next_permutation返回 False 之前的那一个如果只在循环体内收集就会漏掉初始排列或者最终排列。解决先把初始排列加入结果再进入循环。或者用 do-while 结构先收集再判断是否继续。4.3 现象有重复元素时输出重复排列原因使用了基于交换的递归或迭代算法但没有去重逻辑。交换法在遇到相同元素时会产生重复分支。解决要么改用字典序法天然去重要么在交换前加判断如果nums[i] nums[start]且 i ! start则跳过。更稳妥的做法是先排序然后在每层递归中跳过相邻重复元素。4.4 现象N 较大时程序卡死或内存暴涨原因全排列数量是 N!N10 就是 362 万N12 是 4.79 亿。如果一次性把所有排列存进内存N 稍微大一点就会 OOM。解决改成生成器模式每次只产出一个排列由调用方决定是否继续。Python 里用yieldC 里用回调函数Java 里用 Iterator 模式。字典序法天然适合改造成生成器因为它每次只依赖当前排列就能算出下一个。4.5 现象栈模拟版本输出顺序和递归版本不一致原因栈的压入顺序和递归的循环顺序没有对齐。递归是 for 循环从左到右栈模拟时如果压栈顺序反了弹出顺序就会变成从右到左。解决明确栈是 LIFO 结构。如果要模拟从左到右的循环压栈时应该从右往左压或者用一个 idx 变量记录当前层处理到哪而不是一次性把所有候选压入。上面 3.2 节的实现用的是后者更省空间也更清晰。5. 进阶技巧把字典序法改成流式生成器并验证正确性5.1 生成器版本内存 O(1) 的排列流实际工程里我很少一次性返回所有排列。更常见的需求是给我一个回调或者给我一个迭代器我逐个处理。下面是把字典序法改成 Python 生成器的版本def permutation_stream(n): 流式生成 1..n 的全排列每次 yield 一个内存占用 O(n) a list(range(1, n 1)) while True: yield a[:] # 找下一个排列 i n - 2 while i 0 and a[i] a[i 1]: i - 1 if i 0: return j n - 1 while a[j] a[i]: j - 1 a[i], a[j] a[j], a[i] left, right i 1, n - 1 while left right: a[left], a[right] a[right], a[left] left 1 right - 1 # 使用示例只取前 5 个排列 count 0 for p in permutation_stream(10): print(p) count 1 if count 5: break这个版本的好处是即使 N10362 万排列你也可以只取前几个就退出内存始终只有一个数组的开销。生成器的yield a[:]同样做了切片拷贝保证外部拿到的快照不会被后续修改影响。5.2 用阶乘进制验证排列数量和序号验证非递归全排列是否正确一个很有效的方法是用阶乘进制Factoradic做交叉验证。N 个元素的全排列有 N! 个每个排列可以映射到一个 0 到 N!-1 的序号。字典序法的输出顺序恰好对应序号递增。NN!字典序第 0 个字典序第 N!-1 个36[1,2,3][3,2,1]424[1,2,3,4][4,3,2,1]5120[1,2,3,4,5][5,4,3,2,1]你可以写一个简单的测试生成 N5 的全部 120 个排列检查第一个是否是升序、最后一个是否是降序、总数是否等于 120、有没有重复。这四个检查全过基本可以确认实现正确。5.3 一个我踩过的坑整数溢出与索引越界最后说一个血泪经验。在 C/C 里写字典序法时i n - 2这行如果 n 是size_t类型无符号当 n1 时n-2会变成一个巨大的正数导致数组越界访问。这个 bug 在 Python 里不存在因为 Python 整数不会溢出但移植到 C 时非常容易忽略。解决办法很简单先把 n 转成有符号整数或者在最前面加一个if (n 1) return false;的边界判断。我现在的习惯是任何涉及n-1、n-2的索引计算先确认 n 的类型和最小值再动手写循环。这个习惯帮我省掉了至少三次深夜调试。另一个习惯是写完非递归版本后一定拿 N3 和 N4 的手算结果对一遍。N3 只有 6 个排列N4 只有 24 个肉眼就能看完。如果这 30 个结果都对N 更大的情况基本不会错——因为字典序法的逻辑是局部的不依赖 N 的大小。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/15 15:42:32 · 阅读 1.2k 非递归全排列：字典序算法与显式栈模拟实战
简介这份资源聚焦计算机科学中的经典问题——N个数全排列的非递归实现面向正在学习算法与数据结构、希望摆脱递归思维定式或规避栈溢出风险的编程学习者。资源以C源码形式呈现通过迭代与回溯思路完成排列生成可用于算法教学演示、数据处理工具开发或面试刷题参考。压缩包内共1个文件为cpp源代码文件整体仅879B体量轻巧便于直接阅读与移植。目前已有625人学习下载说明该实现具备一定的参考价值。读者可从中获取非递归全排列的核心代码框架理解初始化、循环遍历、元素交换、结果记录与回溯调整等关键环节并借鉴避免重复排列的标记思路。代码结构紧凑适合作为算法课程作业、竞赛模板或工程中排列枚举模块的起点也可在此基础上扩展为字典序输出或去重版本。1. 全排列非递归为什么递归写得好好的我还要把它拆掉写全排列这件事递归版本几乎是所有人的第一反应交换、递归、回溯三行核心代码就能跑。但真把它放进生产环境问题就来了。N 稍微大一点比如 N12递归深度直接顶到 12 层每层还要保存局部变量和返回地址N15 时栈帧开销开始明显拖慢速度如果跑在嵌入式设备或者对栈空间有硬限制的环境里递归版本甚至可能直接崩掉。更麻烦的是递归天然不适合做「下一个排列」这种增量式输出——你没法在任意时刻暂停、保存状态、下次接着跑。非递归全排列解决的正是这个问题用显式的状态变量替代函数调用栈把「生成下一个排列」变成一个可以随时中断、随时恢复的循环过程。它适合三类人一是需要在资源受限环境里跑排列枚举的嵌入式开发者二是要做排列流式输出、不想一次性算完的场景三是想真正理解字典序排列生成逻辑、而不是靠递归「黑匣子」蒙混过关的学习者。下面我从字典序算法讲到自实现栈模拟把参数、边界和踩坑点全部摊开。2. 字典序下一个排列非递归方案里最稳的一条路2.1 为什么字典序法是非递归的首选非递归生成全排列有好几种思路字典序法、递归转栈模拟、Johnson-Trotter 邻位交换法、堆算法Heaps algorithm的迭代版。这几种里我一般首推字典序法原因有三。第一它天然按从小到大输出结果有序方便做二分查找或者提前终止。第二它每次只做「找逆序对 → 交换 → 反转后缀」三步逻辑清晰没有隐藏状态。第三它不依赖任何额外数据结构空间复杂度 O(1)不算输出数组本身这在内存紧张的场合很关键。Johnson-Trotter 虽然每步只交换一对相邻元素理论交换次数最少但它需要维护每个元素的移动方向标记状态管理反而更绕。堆算法的迭代版交换次数也少但输出顺序是乱的不适合需要有序枚举的场景。所以综合来看字典序法是工程上最平衡的选择。2.2 字典序算法的三个核心步骤先把算法逻辑说清楚。给定一个排列要找到字典序意义下的「下一个更大排列」分三步从右往左找第一个升序对找到最大的索引 i使得 a[i] a[i1]。如果找不到说明当前已经是最大排列完全降序整个枚举结束。从右往左找第一个大于 a[i] 的元素找到最大的索引 j使得 a[j] a[i]。因为 a[i1..n-1] 是降序的所以从右往左第一个大于 a[i] 的就是我们要找的。交换 a[i] 和 a[j]然后反转 a[i1..n-1]交换后后缀仍然是降序反转它就变成升序得到恰好比原排列大的下一个排列。这三步的正确性来自字典序的定义要让排列变大必须从最靠右的位置开始调整找到最靠右的可增大位置 i用后缀中刚好比它大的元素替换再把后缀压到最小升序就得到了下一个排列。2.3 用 Python 跑通最小可复现版本下面是一个完整的 Python 实现包含排列生成和调用示例def next_permutation(a): 原地修改数组 a返回 True 表示还有下一个排列False 表示已到最大 n len(a) # 步骤1从右往左找第一个升序对 a[i] a[i1] i n - 2 while i 0 and a[i] a[i 1]: i - 1 if i 0: return False # 已经是完全降序没有下一个了 # 步骤2从右往左找第一个大于 a[i] 的元素 j n - 1 while a[j] a[i]: j - 1 # 步骤3交换 a[i] 和 a[j] a[i], a[j] a[j], a[i] # 步骤4反转 a[i1..n-1]使其变为升序 left, right i 1, n - 1 while left right: a[left], a[right] a[right], a[left] left 1 right - 1 return True def all_permutations(n): 生成 1..n 的全排列按字典序输出 a list(range(1, n 1)) results [a[:]] # 第一个排列 while next_permutation(a): results.append(a[:]) return results if __name__ __main__: perms all_permutations(4) for p in perms: print(p) print(f共 {len(perms)} 个排列)这段代码里next_permutation是核心它原地修改数组并返回布尔值。all_permutations先记录初始升序排列然后不断调用next_permutation直到返回 False。注意results.append(a[:])里的切片操作如果不切片直接 append(a)所有结果都会指向同一个列表对象最后全变成同一个排列——这是新手最容易翻车的地方。2.4 关键参数与边界条件参数/条件含义注意事项n 0空数组应直接返回空结果不要进入循环n 1单元素只有一个排列next_permutation 立即返回 False完全降序输入如 [3,2,1]算法应返回 False表示无下一个排列重复元素如 [1,1,2]字典序法天然去重输出不重复排列i 的初始值n-2从倒数第二个元素开始比较j 的查找条件a[j] a[i]严格大于不是大于等于重复元素这一点值得展开说。如果数组里有重复值字典序法仍然正确因为步骤 1 找的是严格升序对a[i] a[i1]步骤 2 找的是严格大于 a[i] 的元素等于的情况会被跳过。所以 [1,1,2] 只会生成 [1,1,2]、[1,2,1]、[2,1,1] 三个排列不会重复。这是字典序法相比交换法的一个明显优势——交换法需要额外用集合去重。3. 不用字典序也行用显式栈模拟递归过程3.1 什么时候该放弃字典序法字典序法虽好但它有一个前提你必须能定义「下一个排列」的偏序关系。如果题目要求的是按某种自定义顺序输出排列或者你需要在生成过程中做剪枝比如回溯类问题字典序法就不够灵活了。这时候更通用的做法是把递归过程用显式栈模拟出来。递归的本质是系统帮你维护了一个调用栈每个栈帧保存了当前处理到哪一层、循环变量走到哪、以及局部状态。非递归化就是自己用一个栈结构把这些信息存起来用一个循环驱动。3.2 显式栈模拟的通用模板以「依次为每个位置选择一个未使用的数」为例递归版本是这样的def permute_recursive(nums, path, used, result): if len(path) len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) permute_recursive(nums, path, used, result) path.pop() used[i] False把它改成显式栈版本核心是把「当前处理到第几个位置」和「这个位置下一个要尝试的候选索引」压入栈def permute_iterative(nums): n len(nums) result [] used [False] * n path [] # 栈中每个元素: (当前层索引, 下一个候选元素索引) stack [(0, 0)] while stack: depth, idx stack.pop() # 如果这一层已经选好了元素先回退状态 if depth len(path): # 回退把上一轮选的元素标记为未使用 removed path.pop() used[removed] False # 从 idx 开始找下一个可用元素 found False for i in range(idx, n): if not used[i]: used[i] True path.append(i) if len(path) n: result.append([nums[k] for k in path]) # 到达叶子回退 path.pop() used[i] False else: # 压入当前层的下一个候选再压入下一层 stack.append((depth, i 1)) stack.append((depth 1, 0)) found True break # 如果这一层没有更多候选自然结束栈中已无本层记录 return result这段代码比字典序版本复杂不少但它的优势在于通用性你可以在if len(path) n之前插入任意剪枝条件也可以在压栈时调整候选顺序来实现自定义枚举顺序。3.3 栈模拟版本的状态管理要点写显式栈版本时有三个状态必须同步维护used 数组标记哪些元素已经被选入当前路径。每次入栈选元素时置 True回退时置 False。path 列表当前路径。入栈时 append回退时 pop。栈帧中的 idx记录当前层下一次应该从哪个候选开始尝试避免重复枚举。最容易出错的地方是回退时机。在上面的实现里每次从栈中弹出一个(depth, idx)时如果depth len(path)说明这一层之前已经选过元素了需要先把那个元素回退掉。这个判断条件依赖 path 的长度和 depth 的关系写反了就会导致状态错乱。另一个坑是栈的压入顺序。因为栈是后进先出如果要先处理下一层必须先把「当前层的下一个候选」压入再把「下一层的起始帧」压入。顺序反了就会变成深度优先变成广度优先输出顺序完全不对。4. 避坑与排查非递归全排列最容易翻车的五个地方4.1 现象输出结果全部相同原因在把 path 加入 result 时没有做拷贝直接 append 了 path 的引用。后续 path 被修改result 里所有元素都跟着变。解决Python 里用result.append(path[:])或result.append(list(path))C 里用result.push_back(vectorint(path))Java 里用result.add(new ArrayList(path))。一句话存快照不存引用。4.2 现象字典序法漏掉了最后一个排列原因循环条件写成了while next_permutation(a):然后在循环体里收集但初始排列没有单独收集。最后一个排列是在next_permutation返回 False 之前的那一个如果只在循环体内收集就会漏掉初始排列或者最终排列。解决先把初始排列加入结果再进入循环。或者用 do-while 结构先收集再判断是否继续。4.3 现象有重复元素时输出重复排列原因使用了基于交换的递归或迭代算法但没有去重逻辑。交换法在遇到相同元素时会产生重复分支。解决要么改用字典序法天然去重要么在交换前加判断如果nums[i] nums[start]且 i ! start则跳过。更稳妥的做法是先排序然后在每层递归中跳过相邻重复元素。4.4 现象N 较大时程序卡死或内存暴涨原因全排列数量是 N!N10 就是 362 万N12 是 4.79 亿。如果一次性把所有排列存进内存N 稍微大一点就会 OOM。解决改成生成器模式每次只产出一个排列由调用方决定是否继续。Python 里用yieldC 里用回调函数Java 里用 Iterator 模式。字典序法天然适合改造成生成器因为它每次只依赖当前排列就能算出下一个。4.5 现象栈模拟版本输出顺序和递归版本不一致原因栈的压入顺序和递归的循环顺序没有对齐。递归是 for 循环从左到右栈模拟时如果压栈顺序反了弹出顺序就会变成从右到左。解决明确栈是 LIFO 结构。如果要模拟从左到右的循环压栈时应该从右往左压或者用一个 idx 变量记录当前层处理到哪而不是一次性把所有候选压入。上面 3.2 节的实现用的是后者更省空间也更清晰。5. 进阶技巧把字典序法改成流式生成器并验证正确性5.1 生成器版本内存 O(1) 的排列流实际工程里我很少一次性返回所有排列。更常见的需求是给我一个回调或者给我一个迭代器我逐个处理。下面是把字典序法改成 Python 生成器的版本def permutation_stream(n): 流式生成 1..n 的全排列每次 yield 一个内存占用 O(n) a list(range(1, n 1)) while True: yield a[:] # 找下一个排列 i n - 2 while i 0 and a[i] a[i 1]: i - 1 if i 0: return j n - 1 while a[j] a[i]: j - 1 a[i], a[j] a[j], a[i] left, right i 1, n - 1 while left right: a[left], a[right] a[right], a[left] left 1 right - 1 # 使用示例只取前 5 个排列 count 0 for p in permutation_stream(10): print(p) count 1 if count 5: break这个版本的好处是即使 N10362 万排列你也可以只取前几个就退出内存始终只有一个数组的开销。生成器的yield a[:]同样做了切片拷贝保证外部拿到的快照不会被后续修改影响。5.2 用阶乘进制验证排列数量和序号验证非递归全排列是否正确一个很有效的方法是用阶乘进制Factoradic做交叉验证。N 个元素的全排列有 N! 个每个排列可以映射到一个 0 到 N!-1 的序号。字典序法的输出顺序恰好对应序号递增。NN!字典序第 0 个字典序第 N!-1 个36[1,2,3][3,2,1]424[1,2,3,4][4,3,2,1]5120[1,2,3,4,5][5,4,3,2,1]你可以写一个简单的测试生成 N5 的全部 120 个排列检查第一个是否是升序、最后一个是否是降序、总数是否等于 120、有没有重复。这四个检查全过基本可以确认实现正确。5.3 一个我踩过的坑整数溢出与索引越界最后说一个血泪经验。在 C/C 里写字典序法时i n - 2这行如果 n 是size_t类型无符号当 n1 时n-2会变成一个巨大的正数导致数组越界访问。这个 bug 在 Python 里不存在因为 Python 整数不会溢出但移植到 C 时非常容易忽略。解决办法很简单先把 n 转成有符号整数或者在最前面加一个if (n 1) return false;的边界判断。我现在的习惯是任何涉及n-1、n-2的索引计算先确认 n 的类型和最小值再动手写循环。这个习惯帮我省掉了至少三次深夜调试。另一个习惯是写完非递归版本后一定拿 N3 和 N4 的手算结果对一遍。N3 只有 6 个排列N4 只有 24 个肉眼就能看完。如果这 30 个结果都对N 更大的情况基本不会错——因为字典序法的逻辑是局部的不依赖 N 的大小。希望帮到你。本文还有配套的精品资源点击获取