《程序员数学：排列》有重复与无重复排列的 Java 递归实现与复杂度解析
【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总，旨在为大家提供一个清晰详细的学习教程，侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助，请给予支持(关注、点赞、分享)！项目地址: https://gitcode.com/gh_mirrors/code/CodeGuide
排列（Permutation）是高中阶段最常见的组合数学问题之一：给定
n个元素，在“可重复使用”与“不可重复使用”两种约束下，分别能组成多少种、以及如何枚举出全部排列结果。本文以 CodeGuide 仓库中 排列算法文档 为核心骨架，完整讲解n!与n^r两条计数公式背后的 Java 递归实现，并结合仓库内阶乘、组合、笛卡尔积等同系列算法文档进行纵向对照，帮助你既会算、也能写、更能分析复杂度。
一、前言：从“高中排列题”到“程序员算法”
有A、B、C三个字母，允许重复使用字母与不允许重复使用字母，分别有多少种组合方式？这是高中阶段非常常见的数学问题，答案可以用公式直接算出：
- 不可重复，组合数：
n * (n-1) * (n - 2) * ... * 1 = n! - 可重复，组合数：
n * n * n ...（共 r 次）= n^r
例如{1, 2, 3}三个元素：
- 无重复排列（全排列）数量为
3! = 6； - 有重复排列（长度为 2）数量为
3^2 = 9。
这类计算本身并不难，但作为程序员，我们常常需要把这样的数学问题用代码逻辑真实地枚举出来——即不仅算出“有多少种”，还要把每一种排列结果都构造出来。同时，还需要考虑一个核心问题：时间复杂度。
本文接下来就以 CodeGuide 仓库中 排列算法文档 给出的两份 Java 实现为主线，逐行拆解其递归过程，并验证运行结果。
二、数学基础：排列计数公式与阶乘的关系
排列问题的本质是“从n个不同元素中，按顺序选取r个元素”：
| 约束 | 计数公式 | 含义 |
|---|---|---|
| 无重复排列 | n! / (n - r)!，全排列时为n! | 每个元素最多使用一次，顺序有意义 |
| 有重复排列 | n^r | 每个位置都有n种选择，元素可重复使用 |
其中n!（阶乘）是排列计算的基石，其递推关系为n! = n · (n-1)!，关于阶乘的定义、递归实现与测试，可参考仓库中的 《程序员数学：阶乘》。
理解这两个公式后，就可以进入代码实现环节。需要特别说明的是：方法名才是语义的权威——permutationWithRepetitions对应“有重复排列”，permutationWithoutRepetitions对应“无重复排列”，这一点在原文档的两个小节标题命名上存在倒置，我们以下文的代码与测试输出为准展开。
三、有重复排列：permutationWithRepetitions
1. 完整实现
public static List<List<Integer>> permutationWithRepetitions(int[] permutationOptions, int permutationLength) { if (permutationLength == 1) { List<List<Integer>> result = new ArrayList<>(); for (int permutationOption : permutationOptions) { List<Integer> item = new ArrayList<>(); item.add(permutationOption); result.add(item); } return result; } List<List<Integer>> permutations = new ArrayList<>(); List<List<Integer>> smallerPermutations = permutationWithRepetitions(permutationOptions, permutationLength - 1); for (int currentOption : permutationOptions) { for (List<Integer> smallerPermutation : smallerPermutations) { List<Integer> permutation = new ArrayList<>(); permutation.add(currentOption); permutation.addAll(smallerPermutation); permutations.add(permutation); } } return permutations; }2. 参数与递归逻辑拆解
permutationOptions：可供选择的元素数组；permutationLength：目标排列的长度（即公式中的r），例如从{1, 2, 3}中取长度为 2 的排列。
算法采用自顶向下的递归策略，核心分三步：
- 递归出口（base case）：当
permutationLength == 1时，把permutationOptions中的每个元素分别包装成单元素列表返回，即r = 1时共有n个排列； - 递归降维：先递归调用
permutationWithRepetitions(permutationOptions, permutationLength - 1)，求出所有长度为r-1的“小排列”； - 前插合并：外层遍历
permutationOptions的每一个元素currentOption，把它前插到每一个小排列的最前面，从而生成长度为r的完整排列。
由于每次递归都会把全部n个元素与所有r-1长度的小排列做一次笛卡尔式拼接，最终生成的结果数量恰为n^r，与公式完全吻合。
3. 递归过程示例（{1, 2, 3}，长度 2）
r = 1：返回[1]、[2]、[3]；r = 2：依次取currentOption = 1/2/3，分别前插到[1]/[2]/[3]之前，得到：[1,1] [1,2] [1,3] [2,1] [2,2] [2,3] [3,1] [3,2] [3,3]，共3^2 = 9个。
值得注意的是，这里每一层都会对smallerPermutations做全量重建，ArrayList.addAll存在元素拷贝开销，这部分成本我们在后文“复杂度分析”一节统一量化。
四、无重复排列：permutationWithoutRepetitions
1. 完整实现
public static List<List<Integer>> permutationWithoutRepetitions(int[] permutationOptions) { if (permutationOptions.length == 1) { List<List<Integer>> result = new ArrayList<>(); result.add(List.of(permutationOptions[0])); return result; } List<List<Integer>> permutations = new ArrayList<>(); int[] smallerOptions = new int[permutationOptions.length - 1]; System.arraycopy(permutationOptions, 1, smallerOptions, 0, smallerOptions.length); List<List<Integer>> smallerPermutations = permutationWithoutRepetitions(smallerOptions); int firstOption = permutationOptions[0]; for (List<Integer> smallerPermutation : smallerPermutations) { for (int positionIndex = 0; positionIndex <= smallerPermutation.size(); positionIndex++) { List<Integer> permutationPrefix = new ArrayList<>(smallerPermutation.subList(0, positionIndex)); List<Integer> permutationSuffix = new ArrayList<>(smallerPermutation.subList(positionIndex, smallerPermutation.size())); List<Integer> permutation = new ArrayList<>(permutationPrefix); permutation.add(firstOption); permutation.addAll(permutationSuffix); permutations.add(permutation); } } return permutations; }2. 参数与递归逻辑拆解
permutationOptions：待全排列的元素数组（无重复约束下，排列长度固定为数组长度，因此不需要permutationLength参数）。
算法的思路是经典的“固定首元素 + 插入法”：
- 递归出口：当数组只剩 1 个元素时，直接返回仅包含该元素的列表；
- 拆分首元素：取出
permutationOptions[0]，剩余部分通过System.arraycopy拷贝为smallerOptions； - 递归求解剩余部分：对
smallerOptions递归调用自身，得到所有n-1个元素的全排列； - 逐位置插入：对每一个小排列，依次把首元素插入到下标
0 ~ size（含末尾）的每个可能位置，即构造n种新排列。
因为每个元素只会使用一次，最终生成的结果数量恰为n!。
3. 递归过程示例（{1, 2, 3}）
- 对
{3}递归，返回[3]； - 对
{2, 3}：首元素2插入[3]的 0、1 两个位置，得到[2,3]、[3,2]； - 对
{1, 2, 3}：首元素1分别插入[2,3]的 0、1、2 位置和[3,2]的 0、1、2 位置，得到 6 个全排列：[1,2,3] [2,1,3] [2,3,1] [1,3,2] [3,1,2] [3,2,1]。
这里通过subList加两次拷贝的方式完成“在指定位置插入元素”，实现上避免了手写循环移动数组，逻辑也更贴近“插入”的语义。
五、测试验证与运行结果
原文档给出了两个对应的 JUnit 测试用例，均在{1, 2, 3}上运行：
@Test public void test_permutationWithRepetitions() { int[] permutationOptions = {1, 2, 3}; List<List<Integer>> permutation = Permutations.permutationWithRepetitions(permutationOptions, 2); for (List<Integer> list : permutation) { System.out.println(JSON.toJSONString(list)); } } @Test public void test_permutationWithoutRepetitions() { int[] permutationOptions = {1, 2, 3}; List<List<Integer>> permutation = Permutations.permutationWithoutRepetitions(permutationOptions); for (List<Integer> list : permutation) { System.out.println(JSON.toJSONString(list)); } }有重复排列测试结果（n = 3, r = 2，共 9 个）：
[1,1] [1,2] [1,3] [2,1] [2,2] [2,3] [3,1] [3,2] [3,3] Process finished with exit code 0输出恰好包含[1,1]、[2,2]、[3,3]这类重复使用元素的组合，验证了“可重复”语义，且数量9 = 3^2与公式一致。
对于无重复测试，根据第四节推导的递归过程，{1, 2, 3}的输出应为 6 个全排列（n! = 6），这与高中数学中的全排列结论相互印证；仓库中该系列算法的完整工程代码位于作者开源的java-algorithms项目（Permutations类），感兴趣的读者可以结合 组合算法文档 中的Combinations类对比阅读。
六、与组合、笛卡尔积、幂集的关联区分
排列并非孤立的算法，它是 CodeGuide 仓库algorithm/logic/sets系列“集合运算算法家族”的一员。下表对几个极易混淆的概念做一次集中辨析：
| 算法 | 是否讲究顺序 | 元素是否可重复 | 结果数量 | 仓库文档 |
|---|---|---|---|---|
| 排列（有重复） | 讲究 | 可重复 | n^r | 本文 |
| 排列（无重复） | 讲究 | 不可重复 | n! | 本文 |
| 组合（有/无重复） | 不讲究 | 视场景 | C(n+r-1, r)/C(n, r) | 组合算法 |
| 笛卡尔积 | 讲究（有序对） | 跨集合组合 | |A| × |B| | 笛卡尔积 |
| 幂集 | 不讲究 | 不可重复 | 2^n | 幂集 |
| 洗牌（随机排列） | 讲究 | 不可重复 | n!中的随机一个 | Fisher-Yates 洗牌 |
关键区分点在于：
- 排列 vs 组合：排列中
(A, B)与(B, A)是两种结果（顺序有意义），组合中二者等价。双色球选号属于组合，而“三人排队站法”属于排列。组合的实现通过subList从i开始取剩余元素来天然避免顺序重复，与排列的“逐位置插入”形成鲜明对比； - 排列 vs 笛卡尔积：有重复排列本质上是“同一个集合与自身的 r 次笛卡尔积”的枚举；扑克牌
13 × 4 = 52则是两个不同集合笛卡尔积的经典案例（详见 笛卡尔积文档）； - 排列 vs 幂集：幂集枚举的是“所有子集”（
2^n），不关心元素顺序，可视为比排列更低维度的问题（详见 幂集文档）。
理解了这张“家族图谱”，遇到具体业务问题时就能快速定位该用哪种算法。
七、复杂度分析与工程实践建议
1. 时间复杂度
从源码结构看，两份实现均为“先生成全部结果、一次性返回”的递归枚举：
- 有重复排列：结果总量为
n^r，每构造一个长度为r的结果都需要O(r)的addAll拷贝，因此总时间复杂度为O(r · n^r)； - 无重复排列：结果总量为
n!，每个结果的长度为n，构造时同样伴随O(n)级拷贝，因此总时间复杂度为O(n · n!)； - 空间复杂度：两者都因“全量收集到 List 后返回”而需要
O(n^r)/O(n!)级的存储空间（外加递归栈深度O(r)/O(n)）。
这也是排列类算法最需要警惕的一点：结果数量是指数级乃至阶乘级爆炸的。例如n = 10时无重复排列已达3,628,800个，n = 12时超过4.7 亿个，内存很快就会被耗尽。
2. 工程实践建议
- 小规模枚举：当
n ≤ 8左右时，本文的全量返回实现简单直接、易于测试，适合在单元测试中生成全部排列用例； - 大规模处理：若
n较大，应改为“生成一个、消费一个”的迭代器/回调模式，避免一次性持有全部结果；递归写法也建议改为基于数组原地交换（swap）的经典回溯写法，把空间开销降为O(n)； - 典型应用场景：多维度组合的测试数据生成、密码字典的全排列枚举、商品规格 SKU 的组合爆炸排查、以及线上试卷题目与选项乱序（后者可直接使用 Fisher-Yates 洗牌算法，仅需从
n!种排列中随机取一个，而无需全部枚举）。
八、小结
排列算法看似只是两条高中数学公式的代码化，但其背后包含了递归降维、首元素插入、结果全量枚举与复杂度爆炸等多个值得反复咀嚼的程序员思维点。本文完整覆盖了 原文档 中的两套 Java 实现、参数说明、测试用例与输出结果，并补充了与阶乘、组合、笛卡尔积、幂集等仓库同系列算法的对照关系，以及时间/空间复杂度的定量分析。掌握它，你就掌握了“从数学公式到可运行代码”的完整闭环，也为后续学习回溯算法、状态空间搜索等更复杂的枚举类问题打下了基础。
【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总，旨在为大家提供一个清晰详细的学习教程，侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助，请给予支持(关注、点赞、分享)！项目地址: https://gitcode.com/gh_mirrors/code/CodeGuide
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
