All anagrams of a string

Extremely common interview question. You should be able to write it when you are dreaming

var output = [];
var walker = function(prefix, bag){
  var n = bag.length;
  if(n===0){
    output.push(prefix);
    console.log(prefix);
  }
  for(var i=0; i<n; i++){
    walker(prefix+bag[i], bag.substring(0,i)+bag.substring(i+1,n));   
  }
}; 
walker('','abc');

To find a job, you should really be able to write this when you are dreaming. I am serious.

Well, there are cases that your interviewer wants the following version for performance reasons. You are welcome. The code is largely based on this article. The ideas are:

  • Try each of the letters in turn as the first letter and then find all the permutations of the remaining letters using a recursive call.
 
var output = []; 

var swap = function(arr, from, to){   
  var tmp = arr[from];   
  arr[from] = arr[to];   
  arr[to] = tmp; 
}; 

var walker = function(str, index){   

  if(index>=str.length){
    output.push(str);
    console.log(str);
    return;
  }

  for(var i=index; i<str.length; i++){
    swap(str, index, i);
    walker(str, index+1);
    swap(str, index, i);
  }

};

walker(['a','b','c'], 0);
Standard