Recursive solution : string permutation. Unable to return array of permutation strings in javascript

Question

Here is my js:-

function recPerm(rest, soFar) { 
    var next;
    var remaining;
    var output=[];
    if (rest === '') {
        console.log(soFar); //outputting strings..and this works
        output.push(soFar); 
    } else {

        for (var i = 0; i < rest.length; i++) {
            remaining = rest.substr(0,i) + rest.substr(i+1,rest.length-1);
            next = soFar + rest[i];
            recPerm(remaining, next);
        }

    }
    return output; //returns an empty array in the end
}

var out=recPerm('abc',''); 
console.log(out);  //prints empty array

Recursively, I am trying to print permutations of an input string. I am passing the input string and a blank string which recursively then calls this function with remaining string and next individual char in string to be considered. Inside base case, I am succesfully able to log individual strings . But somehow its not saving it in my array towards the end. Is there something i am missing out in my JS?

inside your function you should do something like output.push(somevalue); — Hitmands
– Hitmands, Commented Aug 7, 2016 at 18:51
Each call to recPerm is creating and returning a new Array, which you're then ignoring in the recursive calls. You'd need to add the content of that returned array to the array in the scope of the caller. — user1106925
– user1106925, Commented Aug 7, 2016 at 18:51
String.prototype.substr() taks length of the sub-string as the second parameter. I guess you might be dong wrong with passing indices to it. — Redu
– Redu, Commented Aug 7, 2016 at 19:26

Hitmands · Accepted Answer · 2016-08-07 19:09:01Z

1

Your problem resides on the output variable, that is private to the recPerm function and when you recursively call recPerm, of course, it will be recreated... I suggest You to pass that variable as parameter:

function recPerm(rest, soFar, output) { 
  var next;
  var remaining;
  output = Array.isArray(output) ? output : [];
  
  if(rest === '') {
    output.push(soFar); 
  } else {

    for (var i = 0; i < rest.length; i++) {
      remaining = rest.substr(0,i) + rest.substr(i+1,rest.length-1);
      next = soFar + rest[i];
      recPerm(remaining, next, output);
    }
    
  }
  
  return output; //returns an empty array in the end
}

var out=recPerm('abc',''); 
console.log(out);

edited Aug 7, 2016 at 19:09

answered Aug 7, 2016 at 18:54

Hitmands

14.2k4 gold badges41 silver badges78 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rajat Bansal Over a year ago

Great solution. Thanks

user1106925 Over a year ago

Post an explanation of your answer. These code-only answers are low-quality.

Collectives™ on Stack Overflow

Recursive solution : string permutation. Unable to return array of permutation strings in javascript

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related