JS关于字符串的全排列算法及内存溢出详解

来源：动视网责编：小采时间：2020-11-27 20:03:06

JS关于字符串的全排列算法及内存溢出详解

JS关于字符串的全排列算法及内存溢出详解:本文主要和大家分享JS关于字符串的全排列算法及内存溢出详解，给定字符串，求出所有由该串内字符组合的全排列。所包含的字符不重复。输入："abc" 输出：["abc","acb","bac","bca&qu

推荐度：

点击下载本文 文档为doc格式

导读JS关于字符串的全排列算法及内存溢出详解:本文主要和大家分享JS关于字符串的全排列算法及内存溢出详解，给定字符串，求出所有由该串内字符组合的全排列。所包含的字符不重复。输入："abc" 输出：["abc","acb","bac","bca&qu

本文主要和大家分享JS关于字符串的全排列算法及内存溢出详解，给定字符串，求出所有由该串内字符组合的全排列。所包含的字符不重复。

输入："abc"

输出：["abc","acb","bac","bca","cab","cba"]

我在实现算法时遇到了一个问题，至今无法解决。但是全排列算法又很重要，所以写这篇文章记录一下。

算法一：递归

算法思想：

当字符串长度为1时，输出该字符串；
当长度大于1时，取字符串的首字母，求出长度-1的串的全排列，将首字母插入每一个排列的任意位置。
算法实现：

function permutate(str) {
 //保存每一轮递归的排列结果
 var result = [];
 //初始条件：长度为1
 if (str.length == 1) {
 return [str]
 } else {
 //求剩余子串的全排列,对每个排列进行遍历
 var preResult = permutate(str.slice(1));
 for (var j = 0; j < preResult.length; j++) {
 for (var k = 0; k < preResult[j].length + 1; k++) {
 //将首字母插入k位置 
 var temp = preResult[j].slice(0, k) + str[0] + preResult[j].slice(k);
 result.push(temp);
 }
 }
 return result;
 }
}

算法应该不难理解吧。但是当传参的字符串是"abcdefghijkl"时，排列用到的空间是12!=479001600，过大的内存占用导致内存溢出。如果你是在自己的PC上执行，那么可以使用node --max-old-space-size=8192来修改内存。但是我需要在Codewars上执行，所以无法修改内存。于是我想的办法是利用尾递归优化。呵呵，Node的尾递归优化？不管了，先试试吧。

算法二：尾递归

function permutate(str,result) {
 'use strict';
 let tempArr = [];
 //终止条件str长度为0
 if (str.length == 0) {
 return result
 } else {
 //第一次递归时，插入首字母
 if(result.length === 0){
 tempArr.push(str[0]);
 }else{
 for (let i = 0; i < result.length; i++) {
 let item = result[i];
 let itemLen = item.length;
 for (let j = 0; j < itemLen+1; j++) {
 let temp = item.slice(0, j) + str[0] + item.slice(j);
 tempArr.push(temp);
 }
 }
 }
 //递归截取了第一个字符的子串
 return permutate(str.slice(0),tempArr);
 }
}
permutate("abcdefghijkl",[]);

函数的第一个参数是本次递归的字符串，第二个参数是前x个字符的全排列结果。
思路是：

每次取当次递归串的第一个字母；
若第二个参数长度为0说明是第一次递归，则初始化本次结果为[首字母]。然后将首字母从递归串中剔除，剩余串传给下一次递归;
之后每一次递归，都取递归串的首字母，将其插入前x个字符的全排列的所有位置，求出x+1个字符的全排列；
递归直到第一个参数为空串，则第二个参数为字符串所有字符的全排列。
可能不太好理解，不过知道这是尾递归就行了。虽然尾递归在ES6的严格模式中才有效，但是，我加上'use strict';后仍然无效。事实上我认为并不是函数调用栈的溢出，而是存放变量的堆溢出。所以，大概是无解了吧。毕竟全排列不管怎么样，空间复杂度都是O(n!)的。

算法三：循环

最后再贴个循环的代码吧，也是没什么用，就当扩展思路了。

function perm(str) {
 let result = [],tempArr = [];
 let subStr = str;
 while (subStr.length !== 0) {
 if (result.length === 0) {
 result.push(str[0]);
 } else {
 for (let i = 0; i < result.length; i++) {
 let item = result[i];
 let itemLen = item.length;
 for (let j = 0; j < itemLen+1; j++) {

 let temp = item.slice(0, j) + subStr[0] + item.slice(j);
 tempArr.push(temp);
 }
 }
 result = tempArr;
 tempArr = [];
 }
 subStr = subStr.slice(1);
 }
 return result;
}

JS关于字符串的全排列算法及内存溢出详解

推荐度：

点击下载本文 文档为doc格式

标签： js 字符串关于js

热门焦点

JS关于字符串的全排列算法及内存溢出详解

JS关于字符串的全排列算法及内存溢出详解

算法一：递归

算法二：尾递归

算法三：循环

JS关于字符串的全排列算法及内存溢出详解

最新推荐

猜你喜欢

热门推荐