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 <p>알고리즘은 이해하기 어렵지 않아야 합니다. 그러나 매개변수 문자열이 <code>"abcdefghijkl"</code>인 경우 정렬에 사용되는 공간은 <code>12!=479001600</code>이며 과도한 메모리 사용으로 인해 메모리 오버플로가 발생합니다. 자신의 PC에서 실행하는 경우 <code>node --max-old-space-size=8192</code>를 사용하여 메모리를 수정할 수 있습니다. 하지만 Codewars에서 실행해야 하므로 메모리를 수정할 수 없습니다. 그래서 내 생각은 꼬리 재귀 최적화를 사용하는 것이 었습니다. 하하, Node의 꼬리 재귀 최적화? 어쨌든 먼저 시도해 보겠습니다. <code>"abcdefghijkl"</code>时，排列用到的空间是<code>12!=479001600</code>，过大的内存占用导致内存溢出。如果你是在自己的PC上执行，那么可以使用<code>node --max-old-space-size=8192</code>来修改内存。但是我需要在Codewars上执行，所以无法修改内存。于是我想的办法是利用尾递归优化。呵呵，Node的尾递归优化？不管了，先试试吧。</p><h1 id="算法二-尾递归">算法二：尾递归</h1><pre class="brush:php;toolbar:false">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 <p>函数的第一个参数是本次递归的字符串，第二个参数是前x个字符的全排列结果。<br>思路是：</p><ol class=" list-paddingleft-2">
<li><p>每次取当次递归串的第一个字母；</p></li>
<li><p>若第二个参数长度为0说明是第一次递归，则初始化本次结果为<code>[首字母]</code>。然后将首字母从递归串中剔除，剩余串传给下一次递归;</p></li>
<li><p>之后每一次递归，都取递归串的首字母，将其插入前x个字符的全排列的所有位置，求出x+1个字符的全排列；</p></li>
<li>
<p>递归直到第一个参数为空串，则第二个参数为字符串所有字符的全排列。</p>
<p>可能不太好理解，不过知道这是尾递归就行了。虽然尾递归在ES6的严格模式中才有效，但是，我加上<code>'use strict';</code></p>알고리즘 2: 꼬리 재귀</li>
<pre class="brush:php;toolbar:false">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 

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

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

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

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

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

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

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