JS의 문자열 전체 배열 알고리즘과 메모리 오버플로에 대한 자세한 설명

이 기사에서는 주로 JS의 문자열에 대한 전체 순열 알고리즘과 메모리 오버플로에 대한 자세한 설명을 공유합니다. 문자열이 주어지면 문자열에 있는 모든 문자 조합의 전체 순열을 찾습니다. 포함된 문자는 반복되지 않습니다.

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

알고리즘을 구현할 때 문제가 발생했는데 여전히 해결할 수 없습니다. 하지만 전체 순열 알고리즘은 매우 중요하므로 이를 기록하기 위해 이 글을 썼습니다.

알고리즘 1: 재귀

알고리즘 아이디어:

1. 문자열의 길이가 1이면 문자열을 출력하고,

2. 길이가 1보다 크면 문자열의 첫 글자를 가져와서 다음을 찾습니다. length -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의 꼬리 재귀 최적화? 어쨌든 먼저 시도해 보겠습니다. "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';

   알고리즘 2: 꼬리 재귀

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

함수의 첫 번째 매개변수는 이 재귀의 문자열이고, 두 번째 매개변수는 첫 번째 x 문자의 전체 배열 결과입니다.
아이디어는 다음과 같습니다.

매번 현재 재귀 문자열의 첫 번째 문자를 가져옵니다.

두 번째 매개변수 길이가 0이면 첫 번째 재귀임을 의미하며 초기화 결과는 다음과 같습니다. code>[첫 글자]. 그런 다음 재귀 문자열에서 첫 번째 문자를 제거하고 나머지 문자열은 다음 재귀로 전달됩니다.

이후의 각 재귀에 대해 재귀 문자열의 첫 번째 문자를 가져와 첫 번째 x 문자의 모든 위치에 삽입합니다. x+1 문자의 전체 순열을 찾습니다.

첫 번째 매개변수가 빈 문자열이 될 때까지 반복되고 두 번째 매개변수는 문자열에 있는 모든 문자의 전체 순열입니다.

이해하기 쉽지 않을 수도 있지만 이것이 꼬리 재귀라는 점만 알아두세요. 꼬리 재귀는 ES6의 엄격 모드에서만 유효하지만 'use strict';를 추가한 후에도 여전히 작동하지 않습니다. 사실 함수 호출 스택의 오버플로가 아니라 변수를 저장하는 힙의 오버플로라고 생각합니다. 따라서 아마도 해결책이 없을 것입니다. 결국, 전체 배열이 무엇이든 공간 복잡도는 O(n!)입니다. 🎜🎜🎜🎜Algorithm 3: Loop🎜🎜마지막으로 루프에 대한 코드를 게시하겠습니다. 쓸모가 없으니 그냥 아이디어의 확장으로 사용하세요. 🎜rrreee🎜관련 권장사항: 🎜🎜🎜JS 전체 순열 및 조합 알고리즘 구현 방법🎜🎜🎜🎜JavaScript🎜🎜🎜🎜JavaScript의 여러 재귀적 전체 순열 알고리즘 예제에 대한 자세한 설명: 전체 순열 및 중복 제거🎜🎜

위 내용은 JS의 문자열 전체 배열 알고리즘과 메모리 오버플로에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!