Javascript:打印字符串的排列超出堆栈内存

Javascript: Printing the permutations of a string exceeds stack memory?

本文关键字：堆栈 内存 排列 打印 字符串 Javascript      更新时间：2023-09-26

我有一种类似于这里的方法，但是，对于我的代码片段，我的内存似乎用完了，字符串为2或3个字符。

这是一个实施问题吗？或者我需要在这里优化我的代码吗？

function swap(string, a_id, b_id){
    var swapped = new String();
    for (var i = 0; i < string.length; i++){
        if (i == a_id)
            swapped += string[b_id];
        else if (i == b_id)
            swapped += string[a_id]
        else
            swapped += string[i];
    }
    return swapped;
}
function permute(index, string){
    if (index == (string.length -1)){
        console.log(string);
    }
    else{
        for (var i = index; i <= string.length-1; i++){
            string = swap( string, i, index );
            permute( i, string );
            string = swap(string, i, index ); // undo it for the next iteration
        }
    }
}
permute(0, "AB");

我注意到您的实现中有一个问题置换中的permute( i, string );没有修改i的值，这意味着它必须以某种方式在循环中的某个地方降低i值才能停止递归。

发现逻辑很难理解，当我看到你链接的实际实现时。

String.prototype.replaceAt=function(index, character) {
    return this.substr(0, index) + character + this.substr(index+character.length);
}
//get new string
function swap(string, leftIndex, iIndex) {
    //console.log(string);
    var charAtL = string.charAt(leftIndex);
    var charAtI = string.charAt(iIndex);
    string = string.replaceAt(leftIndex, charAtI);
    string = string.replaceAt(iIndex, charAtL);
    return string;
}
function permute(string, leftIndex, rightIndex) {
    if (leftIndex == rightIndex) {
        console.log(string);
    } else {
        for(var i = leftIndex; i <= rightIndex; i++) {
            string = swap(string, leftIndex, i);
            permute(string, leftIndex + 1, rightIndex);
            string = swap(string, leftIndex, i);
        }
    }
}
permute("ABC", 0, 2);

我只是重写了整个程序，它运行得很好。检查控制台中的所有排列值。

这是正在工作的小提琴。

相关文章：