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

関数の最初のパラメーターはこの再帰の文字列で、2 番目のパラメーターは最初の x 文字の完全な配置結果です。
アイデアは次のとおりです。

現在の再帰文字列の最初の文字を毎回取得します。

2 番目のパラメータの長さが 0 の場合、それが最初の再帰であることを意味し、初期化結果は次のようになります。コード>[頭文字]コード>。次に、再帰文字列から最初の文字を削除し、残りの文字列を次の再帰に渡します。

の後の再帰ごとに、再帰文字列の最初の文字を取得し、それを最初の x 文字のすべての位置に挿入して検索します。 x+1 文字の完全な順列を取得します。

は、最初のパラメーターが空の文字列になるまで再帰的に実行され、その後、2 番目のパラメーターが文字列内のすべての文字の完全な順列になります。

理解するのは簡単ではないかもしれませんが、これが末尾再帰であることを知ってください。末尾再帰は ES6 の strict モードでのみ有効ですが、'use strict'; を追加した後でも機能しません。実際には、関数呼び出しスタックのオーバーフローではなく、変数を格納するヒープのオーバーフローだと思います。したがって、おそらく解決策はありません。結局のところ、完全な配置がどのようなものであっても、空間の複雑さは O(n!) です。 🎜🎜🎜🎜アルゴリズム 3: ループ🎜🎜 最後に、ループのコードを投稿します。これは役に立ちません。アイデアの拡張として使用してください。 🎜rrreee🎜関連する推奨事項: 🎜🎜🎜JS の完全な置換と組み合わせアルゴリズムの実装方法🎜🎜🎜🎜 JavaScript でのいくつかの再帰的な完全な置換アルゴリズムの例の詳細な説明🎜🎜🎜🎜JavaScript の興味深い質問: 完全な置換と重複排除🎜🎜

以上がJSの文字列の完全配置アルゴリズムとメモリオーバーフローを詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。