JavaScript Permutation Issuse

Question

I am working on permutation str using recursive, but it can not get out of the for loop. Can anyone help for this code? Thank you in advance.

    var permutations = [];
    var words = [];
    function getPerms(str) {
    
        if(str.length == 0) {
            permutations.push("");
            return permutations;
        }
        var first = str.charAt(0);//get the first char
        var reminder = str.slice(1);//remove the first char
        words = getPerms(reminder);
        for(var i = 0; i < words.length; i++) {
            for(var j = 0; j <= words[i].length; j++) {
                var s = insertCharAt(words[i], first, j);
                permutations.push(s);
            }
        }
        return permutations;
    }
    function insertCharAt(word, c, i) {
        var start = word.slice(0, i);
        var end = word.slice(i);
        var result = start + c + end;
        return result;
    }
    console.log(getPerms("abc"));

Can you please describe what you want to achieve and how it's going wrong? "permutation str using recursive" is not descriptive. — Reinstate Monica Cellio, Jan 25 '18 at 17:27
Possible duplicate of [Recursively print all permutations of a string (Javascript)](https://stackoverflow.com/questions/39927452/recursively-print-all-permutations-of-a-string-javascript) — Dennis Tsoi, Jan 25 '18 at 18:17

score 1 · Accepted Answer · answered Jan 25 '18 at 18:55

Your code is fine, except for one issue:

The variables permutations should not be a global variable. You can clearly see this is wrong, by looking at permutations.push(""). This is fine as a temporary result in the deepest level of recursion, but obviously this should not be present in the final result. Yet, because permutations is global, and you never remove anything from it, permutations will keep this "".

The problem gets worse because words gets the permutations reference from the recursive call, and so they point to the very same array! So not only are all previous results iterated, but with an extra character add to them they are pushed again into permutations, which is the same array as words giving you an endless loop: you add to the array you are iterating, and so never get to the end.

The solution is simple:

Make permutations a variable local to the getPerms function. And why not do the same for words when you are at it.

function getPerms(str, depth=0) {
    var words = [];
    var permutations = [];

    if(str.length == 0) {
        permutations.push("");
        return permutations;
    }
    var first = str.charAt(0);//get the first char
    var reminder = str.slice(1);//remove the first char
    words = getPerms(reminder, depth+1);
    for(var i = 0; i < words.length; i++) {
        for(var j = 0; j <= words[i].length; j++) {
            var s = insertCharAt(words[i], first, j);
            permutations.push(s);
        }
    }
    return permutations;
}

function insertCharAt(word, c, i) {
    var start = word.slice(0, i);
    var end = word.slice(i);
    var result = start + c + end;
    return result;
}

console.log(getPerms("abc"));

Be sure to check these solutions offered for this problem.

Ngob · Answer 2 · 2018-01-25T18:26:28.293

The problem is probably at the last call you return permutations and then assign it to words (what you did here is like words = permutation), but this is not an assignement by copy, but by reference (because words and permutations belongs to the same scope + they are array), so from the last call they are the same object (and when the code unstack previous call, they are now the same object). To illustrate, execute the following code. You will see, when you modify words you modify permutations:

var permutations = [];
var words = [];
function getPerms(str) {

    if(str.length == 0) {
        permutations.push("");
        return permutations;
    }
    var first = str.charAt(0);//get the first char
    var reminder = str.slice(1);//remove the first char
    words = getPerms(reminder);
    words.push("foo");
    console.log( permutations);
    return permutations;
}
function insertCharAt(word, c, i) {
    var start = word.slice(0, i);
    var end = word.slice(i);
    var result = start + c + end;
    return result;
}
console.log(getPerms("abc"));

In your code, you loop on words and modify permutation in the same time (so, based on the previous explanation, it is like modifying words and loop on words in the same time), it is this things which create the infinite loop. I did not check if your algo works, I am just pointing code's problem. So I think what you want is:

     function getPerms(str) {

        var permutations = [];
        var words = [];
        if(str.length == 0) {
            permutations.push("");
            return permutations;
        }
        var first = str.charAt(0);//get the first char
        var reminder = str.slice(1);//remove the first char
        words = getPerms(reminder);
        for(var i = 0; i < words.length; i++) {
            for(var j = 0; j <= words[i].length; j++) {
                var s = insertCharAt(words[i], first, j);
                permutations.push(s);
            }
        }
        return permutations;
    }
    function insertCharAt(word, c, i) {
        var start = word.slice(0, i);
        var end = word.slice(i);
        var result = start + c + end;
        return result;
    }
    console.log(getPerms("abc"));

JavaScript Permutation Issuse

2 Answers2