本文主要和大家分享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關於字串的全排列演算法及記憶體溢位詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！
