I'm trying to write a function that does the following:
- takes an array of integers as an argument (e.g. [1,2,3,4])
- creates an array of all the possible permutations of [1,2,3,4], with each permutation having a length of 4
the function below (I found it online) does this by taking a string as an argument, and returning all the permutations of that string
I could not figure out how to modify it to make it work with an array of integers, (I think this has something to do with how some of the methods work differently on strings than they do on integers, but I'm not sure...)
let permArr = [];
let usedChars = [];
function permute(input) {
const chars = input.split("");
for (let i = 0; i < chars.length; i++) {
const ch = chars.splice(i, 1);
usedChars.push(ch);
if (chars.length === 0) {
permArr[permArr.length] = usedChars.join("");
}
permute(chars.join(""));
chars.splice(i, 0, ch);
usedChars.pop();
}
return permArr
};
Note: I'm looking to make the function return arrays of integers, not an array of strings.
I really need the solution to be in JavaScript. I've already figured out how to do this in python
Solution 1
Little late, but like to add a slightly more elegant version here. Can be any array...
function permutator(inputArr) {
var results = [];
function permute(arr, memo) {
var cur, memo = memo || [];
for (var i = 0; i < arr.length; i++) {
cur = arr.splice(i, 1);
if (arr.length === 0) {
results.push(memo.concat(cur));
}
permute(arr.slice(), memo.concat(cur));
arr.splice(i, 0, cur[0]);
}
return results;
}
return permute(inputArr);
}
Adding an ES6 (2015) version. Also does not mutate the original input array. Works in the console in Chrome...
const permutator = (inputArr) => {
let result = [];
const permute = (arr, m = []) => {
if (arr.length === 0) {
result.push(m)
} else {
for (let i = 0; i < arr.length; i++) {
let curr = arr.slice();
let next = curr.splice(i, 1);
permute(curr.slice(), m.concat(next))
}
}
}
permute(inputArr)
return result;
}
So...
permutator(['c','a','t']);
Yields...
[ [ 'c', 'a', 't' ],
[ 'c', 't', 'a' ],
[ 'a', 'c', 't' ],
[ 'a', 't', 'c' ],
[ 't', 'c', 'a' ],
[ 't', 'a', 'c' ] ]
And...
permutator([1,2,3]);
Yields...
[ [ 1, 2, 3 ],
[ 1, 3, 2 ],
[ 2, 1, 3 ],
[ 2, 3, 1 ],
[ 3, 1, 2 ],
[ 3, 2, 1 ] ]
Solution 2
If you notice, the code actually splits the chars into an array prior to do any permutation, so you simply remove the join and split operation
var permArr = [],
usedChars = [];
function permute(input) {
var i, ch;
for (i = 0; i < input.length; i++) {
ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
permArr.push(usedChars.slice());
}
permute(input);
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr
};
document.write(JSON.stringify(permute([5, 3, 7, 1])));Solution 3
The following very efficient algorithm uses Heap's method to generate all permutations of N elements with runtime complexity in O(N!):
function permute(permutation) {
var length = permutation.length,
result = [permutation.slice()],
c = new Array(length).fill(0),
i = 1, k, p;
while (i < length) {
if (c[i] < i) {
k = i % 2 && c[i];
p = permutation[i];
permutation[i] = permutation[k];
permutation[k] = p;
++c[i];
i = 1;
result.push(permutation.slice());
} else {
c[i] = 0;
++i;
}
}
return result;
}
console.log(permute([1, 2, 3]));The same algorithm implemented as a generator with space complexity in O(N):
Performance comparison
Feel free to add your implementation to the following benchmark.js test suite:
Run-time results for Chrome 48:
Solution 4
var inputArray = [1, 2, 3];
var result = inputArray.reduce(function permute(res, item, key, arr) {
return res.concat(arr.length > 1 && arr.slice(0, key)
.concat(arr.slice(key + 1))
.reduce(permute, [])
.map(function (perm) {
return [item].concat(perm);
}) || item);
}, []);
alert(JSON.stringify(result));
Solution 5
I have improved SiGanteng's answer.
Now it is possible to call permute more than once, because permArr and usedChars are cleared each time.
function permute(input) {
var permArr = [],
usedChars = [];
return (function main() {
for (var i = 0; i < input.length; i++) {
var ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
permArr.push(usedChars.slice());
}
main();
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr;
})();
}
Solution 6
Some version inspired from Haskell:
perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ]
function perms(xs) {
if (!xs.length) return [[]];
return xs.flatMap(x => {
// get permutations of xs without x, then prepend x to each
return perms(xs.filter(v => v!==x)).map(vs => [x, ...vs]);
});
// or this duplicate-safe way, suggested by @M.Charbonnier in the comments
// return xs.flatMap((x, i) => {
// return perms(xs.filter((v, j) => i!==j)).map(vs => [x, ...vs]);
// });
// or @user3658510's variant
// return xs.flatMap((x, i) => {
// return perms([...xs.slice(0,i),...xs.slice(i+1)]).map(vs => [x,...vs]);
// });
}
document.write(JSON.stringify(perms([1,2,3])));Solution 7
Most answers to this question use expensive operations like continuous insertions and deletions of items in an array, or copying arrays reiteratively.
Instead, this is the typical backtracking solution:
function permute(arr) {
var results = [],
l = arr.length,
used = Array(l), // Array of bools. Keeps track of used items
data = Array(l); // Stores items of the current permutation
(function backtracking(pos) {
if(pos == l) return results.push(data.slice());
for(var i=0; i<l; ++i) if(!used[i]) { // Iterate unused items
used[i] = true; // Mark item as used
data[pos] = arr[i]; // Assign item at the current position
backtracking(pos+1); // Recursive call
used[i] = false; // Mark item as not used
}
})(0);
return results;
}
permute([1,2,3,4]); // [ [1,2,3,4], [1,2,4,3], /* ... , */ [4,3,2,1] ]
Since the results array will be huge, it might be a good idea to iterate the results one by one instead of allocating all the data simultaneously. In ES6, this can be done with generators:
function permute(arr) {
var l = arr.length,
used = Array(l),
data = Array(l);
return function* backtracking(pos) {
if(pos == l) yield data.slice();
else for(var i=0; i<l; ++i) if(!used[i]) {
used[i] = true;
data[pos] = arr[i];
yield* backtracking(pos+1);
used[i] = false;
}
}(0);
}
var p = permute([1,2,3,4]);
p.next(); // {value: [1,2,3,4], done: false}
p.next(); // {value: [1,2,4,3], done: false}
// ...
p.next(); // {value: [4,3,2,1], done: false}
p.next(); // {value: undefined, done: true}
Solution 8
The following function permutates an array of any type and calls a specified callback function on each permutation found:
/*
Permutate the elements in the specified array by swapping them
in-place and calling the specified callback function on the array
for each permutation.
Return the number of permutations.
If array is undefined, null or empty, return 0.
NOTE: when permutation succeeds, the array should be in the original state
on exit!
*/
function permutate(array, callback) {
// Do the actual permuation work on array[], starting at index
function p(array, index, callback) {
// Swap elements i1 and i2 in array a[]
function swap(a, i1, i2) {
var t = a[i1];
a[i1] = a[i2];
a[i2] = t;
}
if (index == array.length - 1) {
callback(array);
return 1;
} else {
var count = p(array, index + 1, callback);
for (var i = index + 1; i < array.length; i++) {
swap(array, i, index);
count += p(array, index + 1, callback);
swap(array, i, index);
}
return count;
}
}
if (!array || array.length == 0) {
return 0;
}
return p(array, 0, callback);
}
If you call it like this:
// Empty array to hold results
var result = [];
// Permutate [1, 2, 3], pushing every permutation onto result[]
permutate([1, 2, 3], function (a) {
// Create a copy of a[] and add that to result[]
result.push(a.slice(0));
});
// Show result[]
document.write(result);
I think it will do exactly what you need - fill an array called result with the permutations of the array [1, 2, 3]. The result is:
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]
Slightly clearer code on JSFiddle: http://jsfiddle.net/MgmMg/6/
Solution 9
Fastest, most (resorces) effective and most elegant version nowadays (2020)
function getArrayMutations (arr, perms = [], len = arr.length) {
if (len === 1) perms.push(arr.slice(0))
for (let i = 0; i < len; i++) {
getArrayMutations(arr, perms, len - 1)
len % 2 // parity dependent adjacent elements swap
? [arr[0], arr[len - 1]] = [arr[len - 1], arr[0]]
: [arr[i], arr[len - 1]] = [arr[len - 1], arr[i]]
}
return perms
}
const arrayToMutate = [1, 2, 3, 4, 5, 6, 7, 8, 9]
const startTime = performance.now()
const arrayOfMutations = getArrayMutations(arrayToMutate)
const stopTime = performance.now()
const duration = (stopTime - startTime) / 1000
console.log(`${arrayOfMutations.length.toLocaleString('en-US')} permutations found in ${duration.toLocaleString('en-US')}s`)Solution 10
Here's a cool solution
const rotations = ([l, ...ls], right=[]) =>
l !== void 0 ? [[l, ...ls, ...right], ...rotations(ls, [...right, l])] : []
const permutations = ([x, ...xs]) =>
x !== void 0 ? permutations(xs).flatMap((p) => rotations([x, ...p])) : [[]]
console.log(permutations("cat"))Solution 11
Here's a very concise and recursive solution that allows you to input the size of the output permutations similar to the statistical operator nPr. "5 permutation 3". This allows you to get all possible permutations with a specific size.
function generatePermutations(list, size=list.length) {
if (size > list.length) return [];
else if (size == 1) return list.map(d=>[d]);
return list.flatMap(d => generatePermutations(list.filter(a => a !== d), size - 1).map(item => [d, ...item]));
}
generatePermutations([1,2,3])
[[1, 2, 3],[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
generatePermutations([1,2,3],2)
[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
Solution 12
Answer without the need for a exterior array or additional function
function permutator (arr) {
var permutations = [];
if (arr.length === 1) {
return [ arr ];
}
for (var i = 0; i < arr.length; i++) {
var subPerms = permutator(arr.slice(0, i).concat(arr.slice(i + 1)));
for (var j = 0; j < subPerms.length; j++) {
subPerms[j].unshift(arr[i]);
permutations.push(subPerms[j]);
}
}
return permutations;
}
Solution 13
This is an interesting task and and here is my contribution. It's very simple and fast. If interested please bear with me and read on.
If you would like to this job fast, you definitely have to get yourself into dynamical programming. Which means you should forget about recursive approaches. That's for sure...
OK le_m's code which uses the Heap's method seems to be the fastest so far. Well i haven't got a name for my algorithm, i don't know if it's already been implemented or not but it's very simple and fast. As with all dynamical programming approaches we will start with the simplest problem and go for the final result.
Assuming that we have an array of a = [1,2,3] we will start with
r = [[1]]; // result
t = []; // interim result
Then follow these three steps;
- For each item of our
r(result) array we will add the next item of the input array. - We will rotate each item it's length many times and will store each instance at the interim result array
t. (well except for the first one not to waste time with 0 rotation) - Once we finish with all items of
rthe interim arraytshould hold the next level of results so we maker = t; t = [];and carry on up until the length of the input arraya.
So the following are our steps;
r array | push next item to | get length many rotations
| each sub array | of each subarray
-----------------------------------------------------------
[[1]] | [[1,2]] | [[1,2],[2,1]]
----------|-------------------|----------------------------
[[1,2], | [[1,2,3], | [[1,2,3],[2,3,1],[3,1,2],
[2,1]] | [2,1,3]] | [2,1,3],[1,3,2],[3,2,1]]
----------|-------------------|----------------------------
previous t| |
-----------------------------------------------------------
So here is the code
function perm(a){
var r = [[a[0]]],
t = [],
s = [];
if (a.length <= 1) return a;
for (var i = 1, la = a.length; i < la; i++){
for (var j = 0, lr = r.length; j < lr; j++){
r[j].push(a[i]);
t.push(r[j]);
for(var k = 1, lrj = r[j].length; k < lrj; k++){
for (var l = 0; l < lrj; l++) s[l] = r[j][(k+l)%lrj];
t[t.length] = s;
s = [];
}
}
r = t;
t = [];
}
return r;
}
var arr = [0,1,2,4,5];
console.log("The length of the permutation is:",perm(arr).length);
console.time("Permutation test");
for (var z = 0; z < 2000; z++) perm(arr);
console.timeEnd("Permutation test");In multiple test i have seen it resolving the 120 permutations of [0,1,2,3,4] for 2000 times in 25~35ms.
Solution 14
Here is another "more recursive" solution.
function perms(input) {
var data = input.slice();
var permutations = [];
var n = data.length;
if (n === 0) {
return [
[]
];
} else {
var first = data.shift();
var words = perms(data);
words.forEach(function(word) {
for (var i = 0; i < n; ++i) {
var tmp = word.slice();
tmp.splice(i, 0, first)
permutations.push(tmp);
}
});
}
return permutations;
}
var str = 'ABC';
var chars = str.split('');
var result = perms(chars).map(function(p) {
return p.join('');
});
console.log(result);
var output = window.document.getElementById('output');
output.innerHTML = result;<div id="output"></div>Output:
[ 'ABC', 'BAC', 'BCA', 'ACB', 'CAB', 'CBA' ]
Solution 15
My first contribution to the site. Also, according to the tests that I have done, this code runs faster than all the other methods mentioned here before this date, of course it is minimal if there are few values, but the time increases exponentially when adding too many.
var result = permutations([1,2,3,4]);
var output = window.document.getElementById('output');
output.innerHTML = JSON.stringify(result);
function permutations(arr) {
var finalArr = [];
function iterator(arrayTaken, tree) {
var temp;
for (var i = 0; i < tree; i++) {
temp = arrayTaken.slice();
temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]);
if (tree >= arr.length) {
finalArr.push(temp);
} else {
iterator(temp, tree + 1);
}
}
}
iterator(arr, 1);
return finalArr;
};<div id="output"></div>Solution 16
Most of the other answers do not utilize the new javascript generator functions which is a perfect solution to this type of problem. You probably only need one permutation at time in memory. Also, I prefer to generate a permutation of a range of indices as this allows me to index each permutation and jump straight to any particular permutation as well as be used to permutate any other collection.
// ES6 generator version of python itertools [permutations and combinations]
const range = function*(l) { for (let i = 0; i < l; i+=1) yield i; }
const isEmpty = arr => arr.length === 0;
const permutations = function*(a) {
const r = arguments[1] || [];
if (isEmpty(a)) yield r;
for (let i of range(a.length)) {
const aa = [...a];
const rr = [...r, ...aa.splice(i, 1)];
yield* permutations(aa, rr);
}
}
console.log('permutations of ABC');
console.log(JSON.stringify([...permutations([...'ABC'])]));
const combinations = function*(a, count) {
const r = arguments[2] || [];
if (count) {
count = count - 1;
for (let i of range(a.length - count)) {
const aa = a.slice(i);
const rr = [...r, ...aa.splice(0, 1)];
yield* combinations(aa, count, rr);
}
} else {
yield r;
}
}
console.log('combinations of 2 of ABC');
console.log(JSON.stringify([...combinations([...'ABC'], 2)]));
const permutator = function() {
const range = function*(args) {
let {begin = 0, count} = args;
for (let i = begin; count; count--, i+=1) {
yield i;
}
}
const factorial = fact => fact ? fact * factorial(fact - 1) : 1;
return {
perm: function(n, permutationId) {
const indexCount = factorial(n);
permutationId = ((permutationId%indexCount)+indexCount)%indexCount;
let permutation = [0];
for (const choiceCount of range({begin: 2, count: n-1})) {
const choice = permutationId % choiceCount;
const lastIndex = permutation.length;
permutation.push(choice);
permutation = permutation.map((cv, i, orig) =>
(cv < choice || i == lastIndex) ? cv : cv + 1
);
permutationId = Math.floor(permutationId / choiceCount);
}
return permutation.reverse();
},
perms: function*(n) {
for (let i of range({count: factorial(n)})) {
yield this.perm(n, i);
}
}
};
}();
console.log('indexing type permutator');
let i = 0;
for (let elem of permutator.perms(3)) {
console.log(`${i}: ${elem}`);
i+=1;
}
console.log();
console.log(`3: ${permutator.perm(3,3)}`);Solution 17
Here's one I made...
const permute = (ar) =>
ar.length === 1 ? ar : ar.reduce( (ac,_,i) =>
{permute([...ar.slice(0,i),...ar.slice(i+1)]).map(v=>ac.push([].concat(ar[i],v))); return ac;},[]);
And here it is again but written less tersely!...
function permute(inputArray) {
if (inputArray.length === 1) return inputArray;
return inputArray.reduce( function(accumulator,_,index){
permute([...inputArray.slice(0,index),...inputArray.slice(index+1)])
.map(value=>accumulator.push([].concat(inputArray[index],value)));
return accumulator;
},[]);
}
How it works: If the array is longer than one element it steps through each element and concatenates it with a recursive call to itself with the remaining elements as it's argument. It doesn't mutate the original array.
Solution 18
Functional answer using flatMap:
const getPermutationsFor = (arr, permutation = []) =>
arr.length === 0
? [permutation]
: arr.flatMap((item, i, arr) =>
getPermutationsFor(
arr.filter((_,j) => j !== i),
[...permutation, item]
)
);
Solution 19
"use strict";
function getPermutations(arrP) {
var results = [];
var arr = arrP;
arr.unshift(null);
var length = arr.length;
while (arr[0] === null) {
results.push(arr.slice(1).join(''));
let less = null;
let lessIndex = null;
for (let i = length - 1; i > 0; i--) {
if(arr[i - 1] < arr[i]){
less = arr[i - 1];
lessIndex = i - 1;
break;
}
}
for (let i = length - 1; i > lessIndex; i--) {
if(arr[i] > less){
arr[lessIndex] = arr[i];
arr[i] = less;
break;
}
}
for(let i = lessIndex + 1; i<length; i++){
for(let j = i + 1; j < length; j++){
if(arr[i] > arr[j] ){
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}
}
}
}
return results;
}
var res = getPermutations([1,2,3,4,5]);
var out = document.getElementById('myTxtArr');
res.forEach(function(i){ out.value+=i+', '});textarea{
height:500px;
width:500px;
}<textarea id='myTxtArr'></textarea>Outputs lexicographically ordered permutations. Works only with numbers. In other case, you have to change the swap method on line 34.
Solution 20
function perm(xs) {
return xs.length === 0 ? [[]] : perm(xs.slice(1)).reduce(function (acc, ys) {
for (var i = 0; i < xs.length; i++) {
acc.push([].concat(ys.slice(0, i), xs[0], ys.slice(i)));
}
return acc;
}, []);
}
Test it with:
console.log(JSON.stringify(perm([1, 2, 3,4])));
Solution 21
#!/usr/bin/env node
"use strict";
function perm(arr) {
if(arr.length<2) return [arr];
var res = [];
arr.forEach(function(x, i) {
perm(arr.slice(0,i).concat(arr.slice(i+1))).forEach(function(a) {
res.push([x].concat(a));
});
});
return res;
}
console.log(perm([1,2,3,4]));
Solution 22
Quite late. Still just in case if this helps anyone.
function permute(arr) {
if (arr.length == 1) return arr
let res = arr.map((d, i) => permute([...arr.slice(0, i),...arr.slice(i + 1)])
.map(v => [d,v].join(''))).flat()
return res
}
console.log(permute([1,2,3,4]))Solution 23
Similar in spirit to the Haskell-style solution by @crl, but working with reduce:
function permutations( base ) {
if (base.length == 0) return [[]]
return permutations( base.slice(1) ).reduce( function(acc,perm) {
return acc.concat( base.map( function(e,pos) {
var new_perm = perm.slice()
new_perm.splice(pos,0,base[0])
return new_perm
}))
},[])
}
Solution 24
This is a very nice use-case for map/reduce:
function permutations(arr) {
return (arr.length === 1) ? arr :
arr.reduce((acc, cv, index) => {
let remaining = [...arr];
remaining.splice(index, 1);
return acc.concat(permutations(remaining).map(a => [].concat(cv,a)));
}, []);
}
- First, we handle the base case and simply return the array if there is only on item in it
- In all other cases
- we create an empty array
- loop over the input-array
- and add an array of the current value and all permutations of the remaining array
[].concat(cv,a)
Solution 25
Here is a minimal ES6 version. The flatten and without functions can be pulled from Lodash.
const flatten = xs =>
xs.reduce((cum, next) => [...cum, ...next], []);
const without = (xs, x) =>
xs.filter(y => y !== x);
const permutations = xs =>
flatten(xs.map(x =>
xs.length < 2
? [xs]
: permutations(without(xs, x)).map(perm => [x, ...perm])
));
Result:
permutations([1,2,3])
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Solution 26
perm = x => x[0] ? x.reduce((a, n) => (perm(x.filter(m => m!=n)).forEach(y => a.push([n,...y])), a), []): [[]]
Solution 27
const permutations = array => {
let permut = [];
helperFunction(0, array, permut);
return permut;
};
const helperFunction = (i, array, permut) => {
if (i === array.length - 1) {
permut.push(array.slice());
} else {
for (let j = i; j < array.length; j++) {
swapElements(i, j, array);
helperFunction(i + 1, array, permut);
swapElements(i, j, array);
}
}
};
function swapElements(a, b, array) {
let temp = array[a];
array[a] = array[b];
array[b] = temp;
}
console.log(permutations([1, 2, 3]));Solution 28
I had a crack at making a version of this that attempts to be concise yet readable, and purely functional programming.
function stringPermutations ([...input]) {
if (input.length === 1) return input;
return input
.map((thisChar, index) => {
const remainingChars = [...input.slice(0, index), ...input.slice(index + 1)];
return stringPermutations(remainingChars)
.map(remainder => thisChar + remainder);
})
.reduce((acc, cur) => [...acc, ...cur]);
}
Note that the argument formatting turns an input string into an array. Not sure if that's a bit too magical.. Not sure I've seen it in the wild. For real readability I'd probably instead do input = [...input] for the first line of the function.
Solution 29
This is an implementation of Heap's algorithm (similar to @le_m's), except it's recursive.
function permute_kingzee(arr,n=arr.length,out=[]) {
if(n == 1) {
return out.push(arr.slice());
} else {
for(let i=0; i<n; i++) {
permute_kingzee(arr,n-1, out);
let j = ( n % 2 == 0 ) ? i : 0;
let t = arr[n-1];
arr[n-1] = arr[j];
arr[j] = t;
}
return out;
}
}
It looks like it's quite faster too : https://jsfiddle.net/3brqzaLe/
Solution 30
This is just little bit more succinct version of delimited's
function permutator (inputArr) {
const result = []
function permute (arr, m = []) {
if (arr.length) {
arr.forEach((item, i) => {
const restArr = [...arr.slice(0, i), ...arr.slice(i + 1)]
permute(restArr, [...m, item])
})
} else {
result.push(m)
}
}
permute(inputArr)
return result
}
