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