《程序员数学：排列》有重复与无重复排列的 Java 递归实现与复杂度解析

《程序员数学排列》有重复与无重复排列的 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对应“无重复排列”这一点在原文档的两个小节标题命名上存在倒置我们以下文的代码与测试输出为准展开。三、有重复排列permutationWithRepetitions1. 完整实现public static ListListInteger permutationWithRepetitions(int[] permutationOptions, int permutationLength) { if (permutationLength 1) { ListListInteger result new ArrayList(); for (int permutationOption : permutationOptions) { ListInteger item new ArrayList(); item.add(permutationOption); result.add(item); } return result; } ListListInteger permutations new ArrayList(); ListListInteger smallerPermutations permutationWithRepetitions(permutationOptions, permutationLength - 1); for (int currentOption : permutationOptions) { for (ListInteger smallerPermutation : smallerPermutations) { ListInteger 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}长度 2r 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存在元素拷贝开销这部分成本我们在后文“复杂度分析”一节统一量化。四、无重复排列permutationWithoutRepetitions1. 完整实现public static ListListInteger permutationWithoutRepetitions(int[] permutationOptions) { if (permutationOptions.length 1) { ListListInteger result new ArrayList(); result.add(List.of(permutationOptions[0])); return result; } ListListInteger permutations new ArrayList(); int[] smallerOptions new int[permutationOptions.length - 1]; System.arraycopy(permutationOptions, 1, smallerOptions, 0, smallerOptions.length); ListListInteger smallerPermutations permutationWithoutRepetitions(smallerOptions); int firstOption permutationOptions[0]; for (ListInteger smallerPermutation : smallerPermutations) { for (int positionIndex 0; positionIndex smallerPermutation.size(); positionIndex) { ListInteger permutationPrefix new ArrayList(smallerPermutation.subList(0, positionIndex)); ListInteger permutationSuffix new ArrayList(smallerPermutation.subList(positionIndex, smallerPermutation.size())); ListInteger 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}; ListListInteger permutation Permutations.permutationWithRepetitions(permutationOptions, 2); for (ListInteger list : permutation) { System.out.println(JSON.toJSONString(list)); } } Test public void test_permutationWithoutRepetitions() { int[] permutationOptions {1, 2, 3}; ListListInteger permutation Permutations.permutationWithoutRepetitions(permutationOptions); for (ListInteger 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(nr-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），仅供参考