Creating JavaScript array permutations

Question

I have an array of n different elements in javascript, I know there are n! possible ways to organize these elements. I want to find out what is the most efficient (fastest) algorithm for generating all possible orders of this array?

I have this code:

var swap = function(array, frstElm, scndElm) { var temp = array[frstElm]; array[frstElm] = array[scndElm]; array[scndElm] = temp; } var permutation = function(array, leftIndex, size) { var x; if(leftIndex === size) { temp = ""; for (var i = 0; i < array.length; i++) { temp += array[i] + " "; } console.log("---------------> " + temp); } else { for(x = leftIndex; x < size; x++) { swap(array, leftIndex, x); permutation(array, leftIndex + 1, size); swap(array, leftIndex, x); } } } arrCities = ["Sidney", "Melbourne", "Queenstown"]; permutation(arrCities, 0, arrCities.length); 

And it works, but I think replacing each element to get combinations is a bit expensive memory, I thought a good way to do this is to just focus on the array indices and get all the permutations of the numbers, I wonder if there is a way to calculate everything from them without having to switch elements inside the array? I think that recursively you can get all of them, I need help for this.

So, for example, if I have:

 arrCities = ["Sidney", "Melbourne", "Queenstown"]; 

I want the output to be:

 [[012],[021],[102],[120],[201],[210]] 

or

 [[0,1,2], [0,2,1], [1,0,2], [1,2,0], [2,0,1], [2,1,0]] 

I read this: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

But Wikipedia never knew how to explain. I do not really understand it, I must say that my mathematical level is not the best.

Answer 1

Using the heap method (you can find in this article the link to which is referenced in your Wikipedia article), you can generate all permutations from N elements with execution complexity in O (N!) And space complexity in O (N). This algorithm is based on swap elements. AFAIK is as fast as it gets, there is no faster method to calculate all permutations.

For implementations and examples, please take a look at my last answer on the relevant question of "permutation in javascript" .

Answer 2

This function, perm(xs) , returns all permutations of the given array:

 const perm=xs=>{let ret=[];for(let i=0;i<xs.length;i=i+1){let rest=perm(xs.slice(0,i).concat(xs.slice(i+1)));if(!rest.length){ret.push([xs[i]])}else{for(let j=0;j<rest.length;j=j+1){ret.push([xs[i]].concat(rest[j]))}}}return ret};