Generate permutations of JavaScript array

Question

I have an array of n different elements in javascript, I know there are n! possible ways to order these elements. I want to know what's the most effective (fastest) algorithm to generate all possible orderings 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 guess swapping every item to get the combinations is a bit expensive memory wise, I thought a good way of doing it is just focusing on the indexes of the array and getting all the permutations of the numbers, I'm wondering if there's a way of computing all of them without having to switch elements within the array? I guess recursively is possible to get all of them, I need help to do so.

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'm reading this: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

But Wikipedia has never been good at explaining. I don't understand much of it, I have to say my math level isn't the best.

Solution 1

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

function 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;
}

console.log(perm([1,2,3]).join("\n"));

Solution 2

Using Heap's method (you can find it in this paper which your Wikipedia article links to), you can generate all permutations of N elements with runtime complexity in O(N!) and space complexity in O(N). This algorithm is based on swapping elements. AFAIK this is as fast as it gets, there is no faster method to calculate all permutations.

For an implementation and examples, please have a look at my recent answer at the related question "permutations in javascript".

Solution 3

It is just for fun - my recursive solve in one string

const perm = a => a.length ? a.reduce((r, v, i) => [ ...r, ...perm([ ...a.slice(0, i), ...a.slice(i + 1) ]).map(x => [ v, ...x ])], []) : [[]]

Solution 4

This is my version based on le_m's code:

function permute(array) {
	Array.prototype.swap = function (index, otherIndex) {
		var valueAtIndex = this[index]

		this[index] = this[otherIndex]
		this[otherIndex] = valueAtIndex
	}

	var result = [array.slice()]

	, length = array.length

	for (var i = 1, heap = new Array(length).fill(0)
		; i < length
	;)
		if (heap[i] < i) {
			array.swap(i, i % 2 && heap[i])
			result.push(array.slice())
			heap[i]++
			i = 1
		} else {
			heap[i] = 0
			i++
		}

	return result
}

console.log(permute([1, 2, 3]))

This is my recursive JavaScript implementation of the same algorithm:

Array.prototype.swap = function (index, otherIndex) {
	var valueAtIndex = this[index]

	this[index] = this[otherIndex]
	this[otherIndex] = valueAtIndex
}

Array.prototype.permutation = function permutation(array, n) {
	array = array || this
	n = n || array.length

	var result = []

	if (n == 1)
		result = [array.slice()]
	else {
		const nextN = n - 1

		for (var i = 0; i < nextN; i++) {
			result.push(...permutation(array, nextN))
			array.swap(Number(!(n % 2)) && i, nextN)
		}

		result.push(...permutation(array, nextN))
	}

	return result
}

console.log([1, 2, 3].permutation())

View more solutions

Comments

[DSB]

What about some method tath doesn't calculate all possible permutations but makes a pretty close calculation?

[le_m]

@DSB I don't think I understand. If you don't want to generate all permutations but just a few, have a look at the Lehmer code which allows you to quickly compute individual permutations given a lexicographic permutation index.

[Paul Grimshaw]

Basic test using this answer (stackoverflow.com/a/37580979/1647737) ran 10 times faster than @chacmoolvm answer above

[18augst]

It takes ages to compute permutations of 11 elements.

[J-Cake]

Okay, I'm just conna say it now, I love one-liners. Thank you so much for this!

[Life after Guest]

Cool but unreadable too