Explication détaillée de l'algorithme d'arrangement complet des chaînes et du débordement de mémoire de JS

Cet article partage principalement avec vous l'algorithme de permutation complet de JS pour les chaînes et une explication détaillée du débordement de mémoire. Étant donné une chaîne, trouvez la permutation complète de toutes les combinaisons de caractères dans la chaîne. Les caractères contenus ne sont pas répétés.

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

J'ai rencontré un problème lors de la mise en œuvre de l'algorithme, que je n'arrive toujours pas à résoudre. Mais l'algorithme de permutation totale est très important, j'ai donc écrit cet article pour l'enregistrer.

Algorithme 1 : Récursion

Idée d'algorithme :

1. Lorsque la longueur de la chaîne est de 1, affichez la chaîne

2. Lorsque la longueur est supérieure à 1, prenez la première lettre de la chaîne, recherchez l'arrangement complet de la chaîne de longueur -1 et insérez la première lettre dans n'importe quelle position de chaque arrangement.

   Implémentation de l'algorithme :

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

L'algorithme ne devrait pas être difficile à comprendre. Mais lorsque la chaîne passée en paramètre est "abcdefghijkl", l'espace utilisé pour l'arrangement est 12!=479001600, et une utilisation excessive de la mémoire entraîne un débordement de mémoire. Si vous exécutez sur votre propre PC, vous pouvez utiliser node --max-old-space-size=8192 pour modifier la mémoire. Mais je dois exécuter sur Codewars, donc la mémoire ne peut pas être modifiée. Mon idée était donc d'utiliser l'optimisation de la récursion de queue. Haha, l'optimisation de la récursivité de la queue de Node ? Peu importe, essayons d’abord.

Algorithme 2 : Récursion de queue

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

Le premier paramètre de la fonction est la chaîne de cette récursion, et le deuxième paramètre est le résultat de l'arrangement complet des x premiers caractères.
L'idée est :

1. Obtenir à chaque fois la première lettre de la chaîne récursive actuelle

2. Si la longueur du deuxième paramètre ; est 0 indique qu'il s'agit de la première récursion, et le résultat de cette initialisation est [首字母]. Supprimez ensuite la première lettre de la chaîne récursive et passez la chaîne restante à la récursion suivante

3. Pour chaque récursion suivante, prenez la première lettre de la chaîne récursive et insérez-la dans le x premiers caractères À toutes les positions de l'arrangement complet, recherchez l'arrangement complet de x+1 caractères

4. de manière récursive jusqu'à ce que le premier paramètre soit une chaîne vide, puis le deuxième paramètre est tout le caractères de la chaîne arrangement complet.

   Ce n'est peut-être pas facile à comprendre, mais sachez simplement qu'il s'agit d'une récursion de queue. Bien que la récursion de queue ne soit valable qu'en mode strict ES6, elle ne fonctionne toujours pas après avoir ajouté 'use strict';. En fait, je pense qu'il ne s'agit pas d'un débordement de la pile d'appels de fonction, mais d'un débordement du tas stockant les variables. Il n’y a donc probablement pas de solution. Après tout, quel que soit l’arrangement complet, la complexité spatiale est O(n !).

Algorithme 3 : Boucle

Enfin, je publierai le code de la boucle. C'est inutile, alors utilisez-le simplement pour élargir vos idées.

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

Recommandations associées :

Méthode de mise en œuvre de l'algorithme de permutation et de combinaison complète JS

Explication détaillée de plusieurs exemples d'algorithmes de permutation complète récursifs en JavaScript

Question amusante JavaScript : Arrangement complet et déduplication

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!