Generate permutations of JavaScript array [duplicate]

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

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

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 ])], []) : [[]]

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

Generate permutations of JavaScript array [duplicate]

Related

Recent Posts