非递归全排列：字典序法原理与C语言实现

简介：面向需要掌握全排列非递归实现的程序员、算法学习者和参加面试的开发者，这份C++源码不依赖递归调用，而用迭代方式演示N个不同元素全排列的完整生成过程，可有效降低递归深度过大带来的栈溢出风险；相比递归方案更节省栈空间，适合用于数据结构课程、算法分析与教育演示。资源包采用RAR压缩，仅包含一个cpp源文件，压缩后约879B，文件结构简单、无多余依赖，便于逐行阅读和二次修改；既可作为教学讲解的示例代码，也可在数据处理或工具开发中直接复用。目前已有625人浏览/学习。代码篇幅虽短，却完整覆盖了数组初始化、双层循环遍历、元素交换、排列记录以及回溯调整等核心步骤，并给出借助哈希表等标记机制避免重复排列的优化思路，有助于快速理解非递归全排列的整体脉络与关键细节，是一份小巧实用的算法参考。

1. N个数全排列的非递归算法：N=12 时递归为什么撑不住

N个数全排列的非递归算法，核心目标是在不借助函数递归的前提下，把 N 个不同元素的全部排列一个不落地生成出来。递归写法三五行就能跑通，但 N 到 12 左右时函数调用开销和数组复制让耗时肉眼可见地飙升，工程里还面临无法暂停、无法恢复的尴尬。字典序法（lexicographic order）是这条路上最经典的非递归方案，配合循环和数组操作就能稳定产出全部 N! 个排列，也是众多算法题库里 next_permutation 的标准底层。这篇文章从原理、实现到参数和踩坑，把这条路线完整拆开，新手可以照着敲，熟手可以跳过前半直接看第五章的坑。

2. 字典序法的生成原理：三步操作如何保证不重不漏

2.1 递归与非递归的分水岭：状态是谁在管

递归版全排列的常见写法是维护 visited 标记数组和 path 路径数组，每层递归选一个没被用过的数放进 path，递归返回后撤销。这套逻辑对 N 小的时候很友好，但执行状态完全挂在系统栈上：每一层的局部变量、循环游标、path 当前长度都由栈帧保存。N 到达 12 的时候，虽然栈深只有 12 层，但总排列数达到 4.79 亿个，每个排列都要经历多层递归调用和数组拷贝，CPU 时间全耗在调用与恢复上。

// 递归版：便于理解，但不适合 N>=12 void dfs(int pos, int n, int *path, int *used) { if (pos == n) { // 得到一个排列，处理 path[0..n-1] return; } for (int v = 0; v < n; v++) { if (!used[v]) { used[v] = 1; path[pos] = v; dfs(pos + 1, n, path, used); // 压栈 used[v] = 0; // 回溯 } } }

这段代码每个节点都要尝试 n 个分支，总尝试次数远大于 n! 本身，大量时间花在递归进入和返回的栈操作上。非递归方案把状态显式放在一个数组里，当前排列就是全部状态，生成下一个排列时只对这个数组做有限次比较和交换，不涉及调用栈。想暂停就保存数组，想恢复就还原数组，控制权完全在调用方手里。这一点在批量生成排列、分片处理、断点续跑的工程场景里是决定性的。

2.2 三步生成后继排列的规则

字典序法的核心操作是把当前排列变成字典序中排在它后面的那一个。给定数组 a[]，操作分三步。

第一步，从右向左扫描，找到第一个满足 a[i] < a[i+1] 的下标 i。这个 i 是拐点，意味着 a[i+1..n-1] 这段子序列已经是降序排列，无法在这段里继续扩大字典序，必须进位到 a[i] 这一位。

第二步，在 i 的右侧从右向左寻找第一个大于 a[i] 的元素 a[j]，交换 a[i] 与 a[j]。交换后 a[i] 变成了比原来大的最小可行值，因为右侧是降序，从右往左找到的第一个大于 a[i] 的元素，就是这个区间里大于 a[i] 的最小值。

第三步，将 a[i+1] 到 a[n-1] 这一段反转。交换后这一段仍然是降序的，反转成升序，恰好是当前前缀下的最小后缀，保证生成的是紧接着的下一个排列。

用一个稍微复杂的例子验证。当前排列 [1,4,3,2]，从右往左扫：i=2 时 3<2 不成立；i=1 时 4<3 不成立；i=0 时 1<4 成立，拐点 i=0。第二步从右往左找大于 1 的元素，j=3 时 a[3]=2>1，交换得到 [2,4,3,1]。第三步反转下标 1 到 3 的子数组 [4,3,1]，得到 [2,1,3,4]。也就是说 [1,4,3,2] 的后继是 [2,1,3,4]，手算字典序也能验证这个结果。

2.3 从数学上确认不重不漏

为什么这套规则能生成全部排列且不重复？关键在两步：每次只动拐点 i 及后缀，前缀 a[0..i-1] 保持不变；后缀被反转成升序，所以得到的排列比当前排列字典序大，且是大于当前排列的最小的那一个。

由于每次生成的都是严格大于当前排列的最小后继，整个生成序列就是从升序排列出发，按字典序逐一遍历，直到完全降序时结束。数学上，任何一个排列都能通过不断找后继的方式到达降序终态，并且途径的排列数量正好是 N!。字典序法的生成序列是一棵单链，没有分支也没有环，这也是它比递归更省内存的另一个原因。

这里有一个容易被忽略的细节：当输入元素不是 0 到 N-1 而是任意 N 个互不相同的数字时，字典序法依然成立。它依赖的只是元素之间的全序关系，与元素本身的值无关。所以对字符串、浮点数、时间戳等类型，只要实现了统一的比较规则，同一套算法可以原样套用。

3. 用 C 语言把非递归全排列跑通：函数拆解与完整代码

3.1 next_permutation 核心函数：拐点、交换、反转

直接给出我常用的实现。这个函数就地修改数组，返回 1 表示生成了下一个排列，返回 0 表示当前已经是最后一个排列。

int next_permutation(int *a, int n) { int i = n - 2; while (i >= 0 && a[i] >= a[i + 1]) { i--; } if (i < 0) { return 0; // 整个序列已经完全降序 } int j = n - 1; while (j > i && a[j] <= a[i]) { j--; } int tmp = a[i]; a[i] = a[j]; a[j] = tmp; int left = i + 1, right = n - 1; while (left < right) { tmp = a[left]; a[left] = a[right]; a[right] = tmp; left++; right--; } return 1; }

函数分四段。第一段 while 找拐点，比较符号是>=，意味着跳过所有降序和相等的情况，直到找到升序。第二段 while 找交换对象，符号是<=，跳过所有小于等于 a[i] 的值，找到第一个大于它的值。第三段交换。第四段用双指针反转后缀。四个段各自独立，任何一段写错都会让结果出错。

参数上，a是 int 数组指针，n是元素个数。如果元素是结构体或字符串，可以把a改成 int 下标数组，比较时用数据本身，交换时仍只交换下标，这样能让交换操作保持 O(1)。注意边界情况：N=1 时，n-2 等于 -1，第一个 while 循环条件 i>=0 不成立，直接返回 0，主循环一次都不进入，这是正确行为；N=2 时，拐点扫描只会检查 i=0 一个位置，生成 [1,2] 的后继 [2,1]。

3.2 主流程设计：while 与 do-while 的取舍

有了核心函数，主流程只需要初始化数组并循环调用。初始状态必须是升序，这是字典序的起点，也是整个算法不漏解的前提。

#include <stdio.h> void print_permutation(int *a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } int main() { int n = 4; int a[4] = {1, 2, 3, 4}; print_permutation(a, n); while (next_permutation(a, n)) { print_permutation(a, n); } return 0; }

这里先打印初始排列，再进入 while 循环。原因很简单：next_permutation 每次生成的是下一个排列，它本身不包含当前排列。如果先循环再打印，初始排列会被漏掉。

另一个常见写法是 do-while：

do { print_permutation(a, n); } while (next_permutation(a, n));

两种写法等价，但 do-while 把先处理当前排列、再生成下一个的顺序写进了结构里，少一条漏打印的路径。我建议在需要处理当前排列的场景里优先用 do-while。注意，在 do-while 版本中，如果初始数组已经是完全降序，循环体依然会执行一次，打印出这个降序排列，然后再调用 next_permutation 返回 0 结束。这符合从任意排列开始都先处理它本身的语义。

3.3 完整可运行版本：支持任意 N 和命令行参数

把函数和主流程拼起来，加上动态内存分配，就是一个可以直接编译运行的工具。用命令行参数控制 N，方便对不同规模做验证。

#include <stdio.h> #include <stdlib.h> int next_permutation(int *a, int n) { int i = n - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; if (i < 0) return 0; int j = n - 1; while (j > i && a[j] <= a[i]) j--; int tmp = a[i]; a[i] = a[j]; a[j] = tmp; int left = i + 1, right = n - 1; while (left < right) { tmp = a[left]; a[left] = a[right]; a[right] = tmp; left++; right--; } return 1; } void print_permutation(int *a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } int main(int argc, char **argv) { int n = 4; if (argc > 1) n = atoi(argv[1]); if (n <= 0) return 1; int *a = (int *)malloc(sizeof(int) * n); for (int i = 0; i < n; i++) a[i] = i + 1; print_permutation(a, n); while (next_permutation(a, n)) print_permutation(a, n); free(a); return 0; }

在命令行执行./perm 5会输出 120 行，./perm 6输出 720 行，这个行数可以直接和 N! 核对。如果行数不对，优先检查核心函数里的两个比较符号；如果只是顺序不对，检查反转操作是否真的把降序后缀变成了升序。编译时建议开-O2优化，对 N 较大的场景有接近一倍的性能提升。

4. 参数与性能：N 多大还能跑，内存占多少

4.1 耗时随 N 的增长曲线：量级预期

全排列的输出规模是 N!，这是任何实现都无法绕开的硬约束。下面给出一组单核 2GHz 左右的实测量级预期，分生成并打印和仅生成不输出两列。

打印是最大的开销来源。printf 加终端渲染比算法本身慢一两个数量级，所以 N>=10 时几乎不会逐条打印，而是把每个排列直接传给下游处理函数，或者写二进制文件。注意这里的耗时是量级估算，不同编译器、不同 CPU、终端是否滚动都会带来数倍差异。实际项目里可以用clock()在循环开始和结束各取一次时间，算出单次排列平均生成耗时，再乘以 N! 得到总预期。

4.2 内存占用与批量处理策略

非递归算法空间复杂度是 O(N)，数组本身占 N 个 int，加上几个下标变量，N=100 时全部内存也不到 1KB。这比递归版本的栈开销更可控，也比某些生成法需要维护的前驱后继链表结构省得多。

处理大规模排列时常见的误区，是先把全部排列收集到内存再统一处理。N=12 时有 4.79 亿个排列，每个排列按 N 个 int 存储需要约 23GB，直接内存爆炸。正确做法是边生成边处理：next_permutation 每产出一个排列，立即消费掉，不保存。如果必须全量保存，可以只存排列的哈希值或编码（例如康托展开），将每个排列压缩为 32 位整数，N=12 时总存储量降到 1.9GB，勉强可接受。

如果数据元素本身是大对象，数组只存下标。交换的是 int 而不是整个对象。我处理 N=10 的字符串全排列时，字符串平均长度 32 字节，直接交换字符串的版本耗时约 3 秒，改用下标交换后降到 0.4 秒，差距主要来自内存拷贝。这个优化在小 N 时感觉不到，N 大时立竿见影。

4.3 重复元素的去重处理

当输入有重复值时，比如 [1,1,2]，期望结果是 112、121、211 三种。标准 next_permutation 默认的去重能力来自两个比较符号：拐点查找用a[i] >= a[i+1]，会跳过相等的相邻对；交换目标查找用a[j] <= a[i]，会跳过相等元素。这样 [1,1,2] 从 i=1 的 1<2 出发，正确生成 [1,2,1] 和 [2,1,1]，不会重复。

如果符号换错，比如拐点查找写成a[i] > a[i+1]，相等元素也会被当成升序，导致 [1,1,2] 里两个 1 被当成了可交换的不同元素，生成重复排列甚至死循环。去重还有一个次要前提：初始数组必须有序，让相同元素相邻排列，跳过的判断才能稳定触发。

5. 避坑指南：五个常见翻车现场与排查方法

5.1 拐点方向找反，生成序列跳着走

现象：生成顺序不是字典序，比如从 1 2 3 4 直接跳到 2 1 3 4，漏掉中间十几个排列。

原因：第一个 while 想从右往左找升序对，但条件写成了a[i] > a[i+1]，找到的是降序位置。用降序位置做拐点，会跳过大量合法排列，导致序列跳变。

解决：条件改成a[i] >= a[i+1]，继续向左移动的条件是不满足升序。排查方法是在拐点扫描后打印 i 的值，手动验证一个简单用例。比如 [1,2,4,3] 从右往左扫：i=2 时 4<3 不成立；i=1 时 2<4 成立，拐点 i=1。如果打印出来 i=3 或 i=0，说明循环方向或比较符号有问题。

5.2 反转后缀写成了排序，算法性质被破坏

现象：排列数量正确，但顺序局部混乱，比如 1 3 2 4 后面直接是 1 4 2 3。

原因：第三步反转被实现成了重新排序。虽然排序也能把小后缀变成升序，但排序会破坏交换后后缀仍是降序这一性质，而如果排序比较器不稳定，排序结果可能不符合字典序要求的严格升序。

解决：交换 a[i] 与 a[j] 之后，后缀仍然保持降序，这是第一步扫描的推论，所以用双指针反向对调即可，不需要排序。把反转封装成单独函数，测试阶段可以在交换前后分别打印数组来确认后缀确实是降序。如果打印出来后缀不是降序，说明第一步的拐点扫描就出了问题，后面全部白做。

5.3 主循环写法漏掉第一个或最后一个排列

现象：N=3 时只输出 5 个，或输出 6 个但第一个不是升序排列。

原因：如果先进入 while 再打印，初始排列被漏掉；如果循环条件写错，在 next_permutation 返回 0 之前强行多调用一次，最后一个降序排列后面又会生成一次垃圾数据。

解决：用 do-while 结构，循环体先处理当前排列，再调用 next_permutation。do-while 天然包含初始排列，也天然在返回 0 时退出，不会多跑。如果必须用 while，记得在循环前单独处理第一个排列，并且不要在返回 0 之后继续调用函数。

5.4 初始数组不是升序，导致排列数不足

现象：把 [2,1,3,4] 作为初始数组输入，输出只有一部分，行数远小于 24。

原因：字典序法从当前排列出发，只生成它的后继。比它字典序小的排列永远不会被生成。所以初始状态必须是全排列中最小的那个，也就是升序排列。

解决：进入算法前先调用排序函数把输入变成升序。如果输入的是 1 到 N 的整数，直接按值排序；如果输入是任意顺序，用 qsort 或手写插入排序都行。排序后如果仍有重复元素，相同值相邻排列，也为去重判断创造了条件。有一个替代方案：如果确实想从中间某个排列出发，可以先跳过前面 K 个排列，而不是改变初始状态。

5.5 N 较大时程序卡住，误判死循环

现象：N=13 跑起来后终端长时间没有输出，或者输出滚动但程序始终不结束，看起来像死循环。

原因：13! 约 62 亿个排列，单核生成加打印需要小时级时间。终端渲染速度远慢于生成速度，所以输出看起来卡住了，但程序其实在正常推进。

解决：先做规模预算。N=13 时不打印，只统计数量或直接处理，并每隔一段时间输出进度条。判断是否死循环的方法是计数而非看输出：在循环体里维护一个计数器，每 100 万个排列打印一次计数，观察数值是否持续增长。如果计数增长且规律接近预期，说明算法正常工作，只是量大。另外注意 N 超过 20 时 N! 已经超过 64 位整数的表示范围，计数变量要改用大整数或浮点估算。

6. 进阶用法：对拍验证、任意起点与第 K 个排列的直接构造

6.1 用对拍验证算法正确性

非递归实现初次写完，最可靠的是对拍：递归版生成结果存文件 A，非递归版存文件 B，两边分别排序后逐行比较。注意递归版本的生成顺序通常不是字典序，取决于选元素次序，所以比较前必须排序。更轻量的方式是只验证数量与集合：确认总行数等于 N!，且每行元素与初始集合一致、无重复。一条命令能完成数量核对：

./perm 6 | sort | uniq | wc -l

如果输出 720，说明数量正确；如果小于 720，说明有重复或遗漏。这条命令把排序和去重都做了，是排查漏解最快的方式。

6.2 从任意排列出发做断点续跑

有些场景不需要从第一个排列开始，比如任务处理到一半中断，要从保存的排列 [3,1,4,2] 继续。直接把数组置为该排列，调用 next_permutation 即可从后继开始。前提是保存的排列本身合法，由初始元素组成且无重复。判断它是否已经是末尾也很简单：调用一次 next_permutation，若返回 0，说明没有后继，任务实际已完成。这个特性是非递归方案独有的一张牌，递归版本想做到同样效果必须序列化整个调用栈，工程成本高得多。

6.3 用阶乘数系统直接构造第 K 个排列

要生成第 K 个排列，不必逐个枚举。将 K-1 做阶乘进制分解，每个数位代表从当前剩余元素中取第几个。例如 N=4，K=10，K-1=9，分解为 9 = 1×3! + 1×2! + 1×1! + 0×0!，系数依次为 1、1、1、0。从初始集合 [1,2,3,4] 出发，取下标 1 对应的 2，剩 [1,3,4]；再取下标 1 对应的 3，剩 [1,4]；取下标 1 对应的 4，剩 [1]；最后取 1，得到 [2,3,4,1]。手算或对照递归输出，第 10 个排列确实是它。

这个技巧在做大规模排列的随机抽样、分页展示时很实用。随机取一个排列时，生成 [0, N!-1] 的随机数 K，再用阶乘数系统直接构造，比从头生成 K 次快得多。实现时注意阶乘会迅速溢出 32 位整数，N>=13 时要用 64 位甚至大整数，否则分解结果会出错。

最后分享一个习惯：我每次写完全排列，第一件事不是看排列长什么样，而是先数行数是不是 N!。数字对不上，再漂亮的输出也是错的；数字对得上，才回去查字典序。这个习惯帮我抓过好几次自己写的 bug。希望帮到你。

本文还有配套的精品资源，点击获取