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

我在實現算法時遇到了一個問題，至今無法解決。但是全排列算法又很重要，所以寫這篇文章記錄一下。

算法一：遞歸

算法思想：

1. 當字符串長度為1時，輸出該字符串；

2. 當長度大于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個字符的全排列結果。
思路是：

1. 每次取當次遞歸串的第一個字母；

2. 若第二個參數長度為0說明是第一次遞歸，則初始化本次結果為[首字母]。然后將首字母從遞歸串中剔除，剩余串傳給下一次遞歸;

3. 之后每一次遞歸，都取遞歸串的首字母，將其插入前x個字符的全排列的所有位置，求出x+1個字符的全排列；

4. 遞歸直到第一個參數為空串，則第二個參數為字符串所有字符的全排列。

   可能不太好理解，不過知道這是尾遞歸就行了。雖然尾遞歸在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全排列組合算法實現方法

Javascript幾種遞歸全排列算法實例詳解

Javascript趣題：全排列去重

以上就是JS關于字符串的全排列算法及內存溢出詳解的詳細內容，更多請關注php中文網其它相關文章！