38

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.

7
  • Please explain what you mean by "most effective". Fastest? Lowest memory usage?
    – Russbear
    Jun 1, 2016 at 22:54
  • There are not n! permutations, unless you are absolutely sure all n elements in the array are different from each other (or, better, discernible). If two elements are indistinguishable you already have less that n! permutations (in fact, you'll have permutations with repetitions).
    – pid
    Jun 1, 2016 at 22:57
  • @EvanTrimboli is not the same, i want to do it by index not by element
    – DSB
    Jun 1, 2016 at 23:49
  • Not really sure how it's different. Replace names with numbers and it's the same problem. Jun 2, 2016 at 0:00
  • @EvanTrimboli that method has to switch the elements within to array to achieve all the permutations which i guess is too expensive speed (and memory) wise, im not good at math but my logic tells me there should be a method to calculate all possible number within a range and doing so would be way faster than having to actually relocate every element
    – DSB
    Jun 2, 2016 at 0:15

5 Answers 5

47

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

0
10

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".

3
  • What about some method tath doesn't calculate all possible permutations but makes a pretty close calculation?
    – DSB
    Jun 4, 2017 at 16:21
  • @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.
    – le_m
    Jun 4, 2017 at 19:00
  • Basic test using this answer (stackoverflow.com/a/37580979/1647737) ran 10 times faster than @chacmoolvm answer above Dec 9, 2017 at 10:14
9

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 ])], []) : [[]]
3
  • 2
    It takes ages to compute permutations of 11 elements.
    – 18augst
    May 14, 2020 at 9:27
  • 1
    Okay, I'm just conna say it now, I love one-liners. Thank you so much for this!
    – J-Cake
    Sep 27, 2020 at 11:33
  • 1
    Cool but unreadable too Dec 15, 2021 at 17:05
2

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

-1
function permutations(str) {
 return (str.length <= 1) ? [str] :
         Array.from(new Set(
           str.split('')
              .map((char, i) => permutations(str.substr(0, i) + str.substr(i + 1)).map(p => char + p))
              .reduce((r, x) => r.concat(x), [])
         ));
}

Not the answer you're looking for? Browse other questions tagged or ask your own question.