Detaillierte Erläuterung des vollständigen Anordnungsalgorithmus von JS für Zeichenfolgen und Speicherüberlauf

In diesem Artikel erfahren Sie hauptsächlich den vollständigen Permutationsalgorithmus von JS für Zeichenfolgen und eine detaillierte Erklärung des Speicherüberlaufs. Finden Sie anhand einer Zeichenfolge die vollständige Permutation aller Zeichenkombinationen in der Zeichenfolge. Die enthaltenen Zeichen werden nicht wiederholt.

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

Ich bin bei der Implementierung des Algorithmus auf ein Problem gestoßen, das ich immer noch nicht lösen kann. Da der Gesamtpermutationsalgorithmus jedoch sehr wichtig ist, habe ich diesen Artikel geschrieben, um ihn aufzuzeichnen.

Algorithmus 1: Rekursion

Algorithmusidee:

1. Wenn die Zeichenfolgenlänge 1 ist, geben Sie die Zeichenfolge aus;

2. Wenn die Länge größer als 1 ist, nehmen Sie den ersten Buchstaben der Zeichenfolge, suchen Sie die vollständige Anordnung der Zeichenfolge mit der Länge -1 und fügen Sie den ersten Buchstaben an einer beliebigen Position jeder Anordnung ein.

   Algorithmusimplementierung:

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

Der Algorithmus sollte nicht schwer zu verstehen sein. Wenn die als Parameter übergebene Zeichenfolge jedoch "abcdefghijkl" ist, ist der für die Anordnung verwendete Speicherplatz 12!=479001600 und eine übermäßige Speichernutzung führt zu einem Speicherüberlauf. Wenn Sie die Ausführung auf Ihrem eigenen PC durchführen, können Sie mit node --max-old-space-size=8192 den Speicher ändern. Aber ich muss Codewars ausführen, damit der Speicher nicht geändert werden kann. Meine Idee war also, die Tail-Rekursionsoptimierung zu verwenden. Haha, Optimierung der Node-Tail-Rekursion? Egal, probieren wir es erst einmal.

Algorithmus 2: Schwanzrekursion

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

Der erste Parameter der Funktion ist die Zeichenfolge dieser Rekursion und der zweite Parameter ist das vollständige Anordnungsergebnis der ersten x Zeichen.
Die Idee ist:

1. Erhalten Sie jedes Mal den ersten Buchstaben der aktuellen rekursiven Zeichenfolge.

2. Wenn die Länge des zweiten Parameters Ist 0, bedeutet dies, dass es sich um die erste Rekursion handelt, und das Ergebnis dieser Initialisierung ist [首字母]. Entfernen Sie dann den ersten Buchstaben aus der rekursiven Zeichenfolge und übergeben Sie die verbleibende Zeichenfolge an die nächste Rekursion.

3. Nehmen Sie für jede weitere Rekursion den ersten Buchstaben der rekursiven Zeichenfolge und fügen Sie ihn in die ein erste x Zeichen Finden Sie an allen Positionen der vollständigen Anordnung die vollständige Anordnung von x+1 Zeichen

4. rekursiv, bis der erste Parameter eine leere Zeichenfolge ist, dann ist der zweite Parameter alle Zeichen der vollständigen Anordnung der Zeichenfolge.

   Es ist vielleicht nicht leicht zu verstehen, aber wissen Sie einfach, dass es sich um eine Schwanzrekursion handelt. Obwohl die Tail-Rekursion nur im strengen ES6-Modus gültig ist, funktioniert sie immer noch nicht, nachdem ich 'use strict'; hinzugefügt habe. Tatsächlich denke ich, dass es sich nicht um einen Überlauf des Funktionsaufrufstapels handelt, sondern um einen Überlauf des Heapspeichers für Variablen. Es gibt also wahrscheinlich keine Lösung. Denn unabhängig von der Gesamtanordnung beträgt die Raumkomplexität O(n!).

Algorithmus 3: Schleife

Zuletzt poste ich den Code für die Schleife. Er ist nutzlos, also verwenden Sie ihn einfach, um Ihre Ideen zu erweitern.

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

Verwandte Empfehlungen:

JS-Methode zur Implementierung des vollständigen Permutations- und Kombinationsalgorithmus

Detaillierte Erläuterung mehrerer Beispiele für rekursive vollständige Permutationsalgorithmen in JavaScript

JavaScript-Spaßfrage: Vollständige Anordnung und Deduplizierung

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung des vollständigen Anordnungsalgorithmus von JS für Zeichenfolgen und Speicherüberlauf. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!