教程文档【免费下载链接】30-seconds-of-codeCoding articles to level up your development skills项目地址https://gitcode.com/gh_mirrors/30/30-seconds-of-code点击查看免费下载生成一个数组所有元素或字符串所有字符的全排列是经典算法问题也是递归思想最直观的练兵场。本文以 30 seconds of code 仓库中的 数组/字符串全排列 一文为主体逐行拆解递归实现、分析其指数级时间复杂度的成因与规避方式并结合仓库内 递归基础、递归性能优化 等姊妹文章帮助你既看得懂这段代码也清楚它什么时候能用、什么时候不能用。读完你将能独立编写数组与字符串两种版本的全排列函数并掌握对其做去重、去重去极限的扩展手段。全排列问题与递归的切入点所谓全排列permutation就是把一个序列的 n 个元素按所有可能的顺序重新排列。n 个互不相同的元素共有n! 种排列。生成全部排列之所以适合递归是因为它满足递归问题的经典特征整体问题的解依赖于更小规模的同类子问题。回顾仓库中 递归概念 一文给出的定义递归是函数的自我重复调用直到触达基准情形base case基准情形负责跳出递归循环若不存在基准情形函数将无限调用自身并导致栈溢出。排列问题的递归思路正是如此固定第一个元素对剩下的 n - 1 个元素求全排列对 n - 1 个元素重复同一策略逐层缩小规模当剩余元素只剩 1 个或 2 个见下文实现细节时基准情形直接给出答案。数组全排列reduce 与 map 的组合实现仓库文档给出了如下实现包含重复元素的情况下也能工作即不去重const permutations arr { if (arr.length 2) return arr.length 2 ? [arr, [arr[1], arr[0]]] : arr; return arr.reduce( (acc, item, i) acc.concat( permutations([...arr.slice(0, i), ...arr.slice(i 1)]).map(val [ item, ...val, ]) ), [] ); }; permutations([1, 33, 5]); // [ [1, 33, 5], [1, 5, 33], [33, 1, 5], [33, 5, 1], [5, 1, 33], [5, 33, 1] ]逐行拆解这段代码基准情形第 2 行当数组长度 2时直接返回。长度为1时返回数组本身唯一排列长度为2时返回[arr, [arr[1], arr[0]]]即原顺序与交换顺序两种排列。Array.prototype.reduce()外层迭代第 36 行遍历当前数组的每个元素item下标i累加器acc初始为[]。对每一个item它把“除去item之外的其余元素”构造为一个新数组[...arr.slice(0, i), ...arr.slice(i 1)]——注意这里通过展开语法复制出新数组而不是原地修改原数组这是保证递归过程中各分支互不干扰的关键。Array.prototype.map()组合第 69 行对“其余元素的全排列”中的每个子排列val将item放到头部得到[item, ...val]即“固定当前元素在前、剩余元素任意排列在后”。acc.concat(...)合并把所有以不同item开头产生的排列拼接成一个完整结果数组。以permutations([1, 33, 5])为例调用树大致如下固定1求[33, 5]的全排列 →[[33, 5], [5, 33]]拼上头得到[[1, 33, 5], [1, 5, 33]]固定33求[1, 5]的全排列 →[[1, 5], [5, 1]]拼上头得到[[33, 1, 5], [33, 5, 1]]固定5求[1, 33]的全排列 →[[1, 33], [33, 1]]拼上头得到[[5, 1, 33], [5, 33, 1]]。最终合并得到 6 种排列恰好是3!。字符串全排列同样的骨架split 与 join 做桥接字符串版本的算法骨架与数组版本完全一致唯一实质差异在于字符与字符串之间的两次转换——用String.prototype.split()把字符串切成字符数组递归完成后再用String.prototype.join()把字符数组拼回字符串const stringPermutations str { if (str.length 2) return str.length 2 ? [str, str[1] str[0]] : [str]; return str .split() .reduce( (acc, letter, i) acc.concat( stringPermutations(str.slice(0, i) str.slice(i 1)).map( val letter val ) ), [] ); }; stringPermutations(abc); // [abc, acb, bac, bca, cab, cba]对照数组版本观察差异环节数组版本字符串版本基准情形长度 2返回[arr, [arr[1], arr[0]]]返回[str, str[1] str[0]]基准情形长度 1返回arr返回[str]迭代载体arr.reduce(...)str.split().reduce(...)去掉第i个元素[...arr.slice(0, i), ...arr.slice(i 1)]str.slice(0, i) str.slice(i 1)组合方式[item, ...val]数组letter val字符串拼接两种版本的基准情形都是长度1或2递归策略都是“固定一个元素 递归求解剩余部分”。abc的输出恰好覆盖全部 6 种排列与数组版本的输出数量一一对应。复杂度分析与“8 到 10 个元素”警戒线原文档特别以警示块强调这两份实现主要用于演示目的生产环境应改用更高效的算法执行时间随元素数量呈指数级增长超过8 到 10 个元素就可能让运行环境卡死。从算法结构可以直接推导出复杂度求解 n 个元素的全排列时每个元素都要递归求解 n - 1 个元素的子问题即递推关系T(n) n × T(n - 1)解得T(n) n!。n! 的增长极为迅速元素个数 n排列数 n!5120672075,040840,3209362,880103,628,800也就是说10个元素的输入会产生超过 362 万条排列且每条排列都要经历一次完整的递归调用与数组/字符串复制。这就是为什么原文档的警戒线设定在 8 到 10 个元素——超过这个规模浏览器或 Node.js 环境很容易因内存与 CPU 消耗过大而失去响应甚至触发调用栈过深的问题。重复元素与去重扩展原文档明确提到数组版本包含重复元素也照常工作如果输入是[1, 1, 2]函数会如实返回重复项导致的多份相同排列共3! 6条其中[1, 1, 2]这类排列会出现两次。这在教学上是合理的“不做额外处理”的设计。若你需要在生产或面试场景下得到去重后的排列可以在此基础上做一层包装用Set对结果去重后转回数组const uniquePermutations arr [...new Set(permutations(arr).map(JSON.stringify))].map(JSON.parse); uniquePermutations([1, 1, 2]).length; // 3而非 6注意这只是一个思路演示JSON.stringify/JSON.parse的序列化方式对对象、嵌套结构并不总是安全。对纯数字或简单值也可以改用元素拼接字符串作为 Set 的键。更彻底的做法是在递归过程中剪枝跳过与当前轮已用元素相同的候选但那属于对本实现的重构不在本文演示范围。递归的代价与优化方向全排列的指数级复杂度在数学上无法回避输出本身就有 n! 条但理解“何时该放弃这种写法”依然重要。仓库中的 递归性能优化 一文以斐波那契数列为例给出了两个通用优化思路记忆化memoization用Map缓存已计算的结果避免同一子问题被重复计算。对排列问题而言子问题之间的重复度较低每个子排列都需要被输出记忆化的收益有限但它能显著改善“同一递归函数被多次调用、参数部分重叠”的场景。改写为迭代从最小实例出发自底向上推导省去函数调用开销与缓存占用的内存。文中指出迭代版本“无缓存、无递归调用与缓存命中检查”执行更省资源。把这两点套用到本主题的结论是全排列的瓶颈在输出规模本身不在调用方式。若业务真的需要列举全部排列且输入较大应优先考虑堆式算法Heaps algorithm等按需生成的迭代方案或根据业务裁剪搜索空间若只是取少量排列则根本不必枚举全部。在 30 seconds of code 仓库中的定位与检索该文档在仓库中拥有明确的“身份证”正文位于 content/snippets/js/s/array-or-string-permutations.md元信息标注tags: [array,string,recursion]属于 JavaScript 语言下的递归主题它被收录进递归专题集合 content/collections/js/recursion.yaml与 递归概念、递归性能优化、阶乘计算 等文章同属一个系列便于按主题连续阅读仓库的 重定向配置 中旧路径/js/s/permutations、/js/s/array-permutations、/js/s/string-permutations均被映射到本文对应的/js/s/array-or-string-permutations说明本文是上述三个旧主题的合并与升级版本。如果你希望沿这条学习路径继续深入建议按 递归概念 → 本文全排列→ 递归性能优化 的顺序阅读先建立“基准情形 自我调用”的心智模型再通过全排列体会“递归分解问题”的实操写法最后理解这类写法的性能边界与改进手段。此外仓库 JavaScript 语言页面 汇总了本文用到的Array.prototype.reduce()、Array.prototype.map()、String.prototype.split()、String.prototype.join()等全部相关 API 的官方参考链接可作为查阅底层语义的补充材料。小结本文完整复刻并拆解了仓库中数组与字符串全排列的两个递归实现二者共享“固定一个元素 递归剩余部分 合并结果”的骨架字符串版本仅多出split/join两次转换同时明确了两点边界——输出数量为 n!、执行时间指数级增长8 到 10 个元素以上不宜在生产中使用若必须处理重复元素可在结果层用Set去重或改用更高效的迭代式生成算法。这份代码作为递归教学素材恰到好处作为生产工具则务必评估输入规模。赞分享教程文档【免费下载链接】30-seconds-of-codeCoding articles to level up your development skills项目地址https://gitcode.com/gh_mirrors/30/30-seconds-of-code点击查看免费下载相关推荐30 Seconds of Code用 Blob 精确计算 JavaScript 字符串字节大小30 Seconds of Code用 Blob 精确计算 JavaScript 字符串字节大小 导读 本文讲解如何精确计算 JavaScript 字符串的字教程文档FreeMoCap 完整指南三步命令从普通视频拿到 3D 动作数据FreeMoCap 完整指南三步命令从普通视频拿到 3D 动作数据 如果你曾想做动作分析却被商用动捕设备的价格和一身反光标记点的穿戴流程劝退可以看看 F教程文档终极JavaScript URL操作指南掌握30-seconds-of-code的高效技巧终极JavaScript URL操作指南掌握30 seconds of code的高效技巧 30 seconds of code是一个基于JavaScript教程文档上一篇MultiHighlight 插件使用指南下一篇Neovim-Qt部署与打包Windows/macOS/Linux多平台发布方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考