Detailed explanation of JS's full arrangement algorithm of strings and memory overflow

This article mainly shares with you JS's full permutation algorithm for strings and detailed explanation of memory overflow. Given a string, find the full permutation of all character combinations in the string. The characters contained are not repeated.

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

I encountered a problem when implementing the algorithm, and I still can't solve it. But the total permutation algorithm is very important, so I wrote this article to record it.

Algorithm 1: Recursive

Algorithm idea:

1. When the length of the string is 1, output the string;

2. When the length is greater than 1, take the first letter of the string, find the full arrangement of the string with length -1, and insert the first letter into any position of each arrangement.

   Algorithm implementation:

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;
    }
}

The algorithm should not be difficult to understand. However, when the parameter string is "abcdefghijkl", the space used for arrangement is 12!=479001600, and excessive memory usage leads to memory overflow. If you are executing on your own PC, you can use node --max-old-space-size=8192 to modify the memory. But I need to execute on Codewars, so the memory cannot be modified. So my idea was to use tail recursion optimization. Haha, Node’s tail recursion optimization? No matter, let’s try it first.

Algorithm 2: Tail recursion

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",[]);

The first parameter of the function is the string of this recursion, and the second parameter is the full arrangement result of the first x characters.
The idea is:

1. Get the first letter of the recursive string each time;

2. If the length of the second parameter is 0 indicates that it is the first recursion, and the initialization result is [first letter]. Then remove the first letter from the recursive string and pass the remaining string to the next recursion;

3. For each subsequent recursion, take the first letter of the recursive string and insert it into the first x characters At all positions of the full arrangement, find the full arrangement of x+1 characters;

4. Recurse until the first parameter is an empty string, then the second parameter is all the characters of the string full arrangement.

   It may not be easy to understand, but just know that this is tail recursion. Although tail recursion is only valid in the strict mode of ES6, it still doesn't work after I add 'use strict';. In fact, I think it is not an overflow of the function call stack, but an overflow of the heap storing variables. So, there is probably no solution. After all, no matter what the full arrangement is, the space complexity is O(n!).

Algorithm 3: Loop

Finally, I’ll post the code for the loop. It’s of no use, so just use it to expand your ideas.

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;
}

Related recommendations:

JS full permutation and combination algorithm implementation method

Detailed explanation of several recursive full permutation algorithm examples in JavaScript

JavaScript fun question: full arrangement and deduplication

The above is the detailed content of Detailed explanation of JS's full arrangement algorithm of strings and memory overflow. For more information, please follow other related articles on the PHP Chinese website!