Permutations in JavaScript?
JavascriptPermutationJavascript Problem Overview
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...)
var permArr = [], usedChars = [];
function permute(input) {
var i, ch, chars = input.split("");
for (i = 0; i < chars.length; i++) {
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
Javascript Solutions
Solution 1 - Javascript
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 - Javascript
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 - Javascript
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):
function* permute(permutation) {
var length = permutation.length,
c = Array(length).fill(0),
i = 1, k, p;
yield permutation.slice();
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;
yield permutation.slice();
} else {
c[i] = 0;
++i;
}
}
}
// Memory efficient iteration through permutations:
for (var permutation of permute([1, 2, 3])) console.log(permutation);
// Simple array conversion:
var permutations = [...permute([1, 2, 3])];
###Performance comparison Feel free to add your implementation to the following benchmark.js test suite:
function permute_SiGanteng(input) {
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
}
return permute(input);
}
function permute_delimited(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);
}
function permute_monkey(inputArray) {
return 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);
}, []);
}
function permute_Oriol(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;
})();
}
function permute_MarkusT(input) {
function permutate(array, callback) {
function p(array, index, callback) {
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);
}
var result = [];
permutate(input, function(a) {
result.push(a.slice(0));
});
return result;
}
function permute_le_m(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;
}
function permute_Urielzen(arr) {
var finalArr = [];
var iterator = function (arrayTaken, tree) {
for (var i = 0; i < tree; i++) {
var 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;
}
function permute_Taylor_Hakes(arr) {
var permutations = [];
if (arr.length === 1) {
return [ arr ];
}
for (var i = 0; i < arr.length; i++) {
var subPerms = permute_Taylor_Hakes(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;
}
var Combinatorics = (function () {
'use strict';
var version = "0.5.2";
/* combinatory arithmetics */
var P = function(m, n) {
var p = 1;
while (n--) p *= m--;
return p;
};
var C = function(m, n) {
if (n > m) {
return 0;
}
return P(m, n) / P(n, n);
};
var factorial = function(n) {
return P(n, n);
};
var factoradic = function(n, d) {
var f = 1;
if (!d) {
for (d = 1; f < n; f *= ++d);
if (f > n) f /= d--;
} else {
f = factorial(d);
}
var result = [0];
for (; d; f /= d--) {
result[d] = Math.floor(n / f);
n %= f;
}
return result;
};
/* common methods */
var addProperties = function(dst, src) {
Object.keys(src).forEach(function(p) {
Object.defineProperty(dst, p, {
value: src[p],
configurable: p == 'next'
});
});
};
var hideProperty = function(o, p) {
Object.defineProperty(o, p, {
writable: true
});
};
var toArray = function(f) {
var e, result = [];
this.init();
while (e = this.next()) result.push(f ? f(e) : e);
this.init();
return result;
};
var common = {
toArray: toArray,
map: toArray,
forEach: function(f) {
var e;
this.init();
while (e = this.next()) f(e);
this.init();
},
filter: function(f) {
var e, result = [];
this.init();
while (e = this.next()) if (f(e)) result.push(e);
this.init();
return result;
},
lazyMap: function(f) {
this._lazyMap = f;
return this;
},
lazyFilter: function(f) {
Object.defineProperty(this, 'next', {
writable: true
});
if (typeof f !== 'function') {
this.next = this._next;
} else {
if (typeof (this._next) !== 'function') {
this._next = this.next;
}
var _next = this._next.bind(this);
this.next = (function() {
var e;
while (e = _next()) {
if (f(e))
return e;
}
return e;
}).bind(this);
}
Object.defineProperty(this, 'next', {
writable: false
});
return this;
}
};
/* power set */
var power = function(ary, fun) {
var size = 1 << ary.length,
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'index');
addProperties(that, {
valueOf: sizeOf,
init: function() {
that.index = 0;
},
nth: function(n) {
if (n >= size) return;
var i = 0,
result = [];
for (; n; n >>>= 1, i++) if (n & 1) result.push(this[i]);
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
},
next: function() {
return this.nth(this.index++);
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* combination */
var nextIndex = function(n) {
var smallest = n & -n,
ripple = n + smallest,
new_smallest = ripple & -ripple,
ones = ((new_smallest / smallest) >> 1) - 1;
return ripple | ones;
};
var combination = function(ary, nelem, fun) {
if (!nelem) nelem = ary.length;
if (nelem < 1) throw new RangeError;
if (nelem > ary.length) throw new RangeError;
var first = (1 << nelem) - 1,
size = C(ary.length, nelem),
maxIndex = 1 << ary.length,
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'index');
addProperties(that, {
valueOf: sizeOf,
init: function() {
this.index = first;
},
next: function() {
if (this.index >= maxIndex) return;
var i = 0,
n = this.index,
result = [];
for (; n; n >>>= 1, i++) {
if (n & 1) result[result.length] = this[i];
}
this.index = nextIndex(this.index);
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* permutation */
var _permutation = function(ary) {
var that = ary.slice(),
size = factorial(that.length);
that.index = 0;
that.next = function() {
if (this.index >= size) return;
var copy = this.slice(),
digits = factoradic(this.index, this.length),
result = [],
i = this.length - 1;
for (; i >= 0; --i) result.push(copy.splice(digits[i], 1)[0]);
this.index++;
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
};
return that;
};
// which is really a permutation of combination
var permutation = function(ary, nelem, fun) {
if (!nelem) nelem = ary.length;
if (nelem < 1) throw new RangeError;
if (nelem > ary.length) throw new RangeError;
var size = P(ary.length, nelem),
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'cmb');
hideProperty(that, 'per');
addProperties(that, {
valueOf: function() {
return size;
},
init: function() {
this.cmb = combination(ary, nelem);
this.per = _permutation(this.cmb.next());
},
next: function() {
var result = this.per.next();
if (!result) {
var cmb = this.cmb.next();
if (!cmb) return;
this.per = _permutation(cmb);
return this.next();
}
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* export */
var Combinatorics = Object.create(null);
addProperties(Combinatorics, {
C: C,
P: P,
factorial: factorial,
factoradic: factoradic,
permutation: permutation,
});
return Combinatorics;
})();
function permute_Technicalbloke(inputArray) {
if (inputArray.length === 1) return inputArray;
return inputArray.reduce( function(accumulator,_,index){
permute_Technicalbloke([...inputArray.slice(0,index),...inputArray.slice(index+1)])
.map(value=>accumulator.push([inputArray[index],value]));
return accumulator;
},[]);
}
var suite = new Benchmark.Suite;
var input = [0, 1, 2, 3, 4];
suite.add('permute_SiGanteng', function() {
permute_SiGanteng(input);
})
.add('permute_delimited', function() {
permute_delimited(input);
})
.add('permute_monkey', function() {
permute_monkey(input);
})
.add('permute_Oriol', function() {
permute_Oriol(input);
})
.add('permute_MarkusT', function() {
permute_MarkusT(input);
})
.add('permute_le_m', function() {
permute_le_m(input);
})
.add('permute_Urielzen', function() {
permute_Urielzen(input);
})
.add('permute_Taylor_Hakes', function() {
permute_Taylor_Hakes(input);
})
.add('permute_Combinatorics', function() {
Combinatorics.permutation(input).toArray();
})
.add('permute_Technicalbloke', function() {
permute_Technicalbloke(input);
})
.on('cycle', function(event) {
console.log(String(event.target));
})
.on('complete', function() {
console.log('Fastest is ' + this.filter('fastest').map('name'));
})
.run({async: true});
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/platform/1.3.4/platform.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>
Run-time results for Chrome 48:
Solution 4 - Javascript
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 - Javascript
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;
})();
}
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;
})();
}
document.write(JSON.stringify(permute([5, 3, 7, 1])));
Solution 6 - Javascript
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 - Javascript
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 - Javascript
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 - Javascript
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 - Javascript
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 - Javascript
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 - Javascript
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 - Javascript
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 - Javascript
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 - Javascript
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 - Javascript
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 - Javascript
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 - Javascript
"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 19 - Javascript
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 20 - Javascript
#!/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 21 - Javascript
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 22 - Javascript
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 23 - Javascript
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 - Javascript
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 - Javascript
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 - Javascript
perm = x => x[0] ? x.reduce((a, n) => (perm(x.filter(m => m!=n)).forEach(y => a.push([n,...y])), a), []): [[]]
Solution 27 - Javascript
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 - Javascript
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 - Javascript
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 - Javascript
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
}
Solution 31 - Javascript
I wrote a post to demonstrate how to permute an array in JavaScript. Here is the code which does this.
var count=0;
function permute(pre,cur){
var len=cur.length;
for(var i=0;i<len;i++){
var p=clone(pre);
var c=clone(cur);
p.push(cur[i]);
remove(c,cur[i]);
if(len>1){
permute(p,c);
}else{
print(p);
count++;
}
}
}
function print(arr){
var len=arr.length;
for(var i=0;i<len;i++){
document.write(arr[i]+" ");
}
document.write("<br />");
}
function remove(arr,item){
if(contains(arr,item)){
var len=arr.length;
for(var i = len-1; i >= 0; i--){ // STEP 1
if(arr[i] == item){ // STEP 2
arr.splice(i,1); // STEP 3
}
}
}
}
function contains(arr,value){
for(var i=0;i<arr.length;i++){
if(arr[i]==value){
return true;
}
}
return false;
}
function clone(arr){
var a=new Array();
var len=arr.length;
for(var i=0;i<len;i++){
a.push(arr[i]);
}
return a;
}
Just call
> permute([], [1,2,3,4])
will work. For details on how this works, please refer to the explanation in that post.
Solution 32 - Javascript
function nPr(xs, r) {
if (!r) return [];
return xs.reduce(function(memo, cur, i) {
var others = xs.slice(0,i).concat(xs.slice(i+1)),
perms = nPr(others, r-1),
newElms = !perms.length ? [[cur]] :
perms.map(function(perm) { return [cur].concat(perm) });
return memo.concat(newElms);
}, []);
}
Solution 33 - Javascript
let permutations = []
permutate([], {
color: ['red', 'green'],
size: ['big', 'small', 'medium'],
type: ['saison', 'oldtimer']
})
function permutate (currentVals, remainingAttrs) {
remainingAttrs[Object.keys(remainingAttrs)[0]].forEach(attrVal => {
let currentValsNew = currentVals.slice(0)
currentValsNew.push(attrVal)
if (Object.keys(remainingAttrs).length > 1) {
let remainingAttrsNew = JSON.parse(JSON.stringify(remainingAttrs))
delete remainingAttrsNew[Object.keys(remainingAttrs)[0]]
permutate(currentValsNew, remainingAttrsNew)
} else {
permutations.push(currentValsNew)
}
})
}
Result:
[ [ 'red', 'big', 'saison' ],
[ 'red', 'big', 'oldtimer' ],
[ 'red', 'small', 'saison' ],
[ 'red', 'small', 'oldtimer' ],
[ 'red', 'medium', 'saison' ],
[ 'red', 'medium', 'oldtimer' ],
[ 'green', 'big', 'saison' ],
[ 'green', 'big', 'oldtimer' ],
[ 'green', 'small', 'saison' ],
[ 'green', 'small', 'oldtimer' ],
[ 'green', 'medium', 'saison' ],
[ 'green', 'medium', 'oldtimer' ]
]
Solution 34 - Javascript
const removeItem = (arr, i) => {
return arr.slice(0, i).concat(arr.slice(i+1));
}
const makePermutations = (strArr) => {
const doPermutation = (strArr, pairArr) => {
return strArr.reduce((result, permutItem, i) => {
const currentPair = removeItem(pairArr, i);
const tempResult = currentPair.map((item) => permutItem+item);
return tempResult.length === 1 ? result.concat(tempResult) :
result.concat(doPermutation(tempResult, currentPair));
}, []);
}
return strArr.length === 1 ? strArr :
doPermutation(strArr, strArr);
}
makePermutations(["a", "b", "c", "d"]);
//result: ["abcd", "abdc", "acbd", "acdb", "adbc", "adcb", "bacd", "badc", "bcad", "bcda", "bdac", "bdca", "cabd", "cadb", "cbad", "cbda", "cdab", "cdba", "dabc", "dacb", "dbac", "dbca", "dcab", "dcba"]
Solution 35 - Javascript
I used a string instead of an array and it seems like my algorithm consumes very less time. I am posting my algorithm here, am I measuring the time correctly?
console.time('process');
var result = []
function swapper(toSwap){
let start = toSwap[0]
let end = toSwap.slice(1)
return end + start
}
function perm(str){
let i = str.length
let filling = i - 1
let buckets = i*filling
let tmpSwap = ''
for(let j=0; j<filling; j++){
if(j===0){
result.push(str)
}else{
if(j === 1){
tmpSwap = swapper(str.slice(1))
result.push(str[0]+ tmpSwap)
if(j === filling-1 && result.length < buckets){
perm(swapper(str))
}
}else{
tmpSwap = swapper(tmpSwap)
result.push(str[0]+ tmpSwap)
if(j === filling-1 && result.length < buckets){
perm(swapper(str))
}
}
}
}
if(result.length = buckets){
return result
}else{
return 'something went wrong'
}
}
console.log(perm('abcdefghijk'))
console.timeEnd('process');
Solution 36 - Javascript
I think perhaps the only difference in my solution below is that I stop the recursion one step before the null case. Hopefully the embedded comments are sufficient explanation.
function Permutations (A) // computes all possible ordered sequences of the entries in array A and returns them as an array of arrays
{
var perms = [];
for (var i = 0 ; i < A.length ; i++)
{
var rem = A.slice (0); // copy input array to retain remainder of elements after removing i'th element
var el = rem.splice (i,1);
if (A.length == 2) {perms.push ([el [0],rem [0]])} // recursion end case
else
{
var sub = Permutations (rem); // recursive call
for (var s = 0 ; s < sub.length ; s++) // process recursive response, adding el to the start of each returned sequence
{
sub [s].splice (0,0,el [0]);
perms.push (sub [s]);
};
};
};
return perms ;
};// end of Permutations function
Solution 37 - Javascript
I think you'll may like this one:
const permute1 = (arr: any[]): any[][] =>
arr.reduce(
(acc, curr) =>
acc.length > 0
? acc
.map((p) =>
Array.from({ length: p.length + 1 }, (_, i) =>
p.slice(0, i).concat(curr, p.slice(i))
)
)
.flat()
: [[curr]],
[]
);
Solution 38 - Javascript
Here's a very short solution, that only works for 1 or 2 long strings. It's a oneliner, and it's blazing fast, using ES6 and not depending on jQuery. Enjoy:
var p = l => l.length<2 ? [l] : l.length==2 ? [l[0]+l[1],l[1]+l[0]] : Function('throw Error("unimplemented")')();
Solution 39 - Javascript
function swap(array1, index1, index2) {
var temp;
temp = array1[index1];
array1[index1] = array1[index2];
array1[index2] = temp;
}
function permute(a, l, r) {
var i;
if (l == r) {
console.log(a.join(''));
} else {
for (i = l; i <= r; i++) {
swap(a, l, i);
permute(a, l + 1, r);
swap(a, l, i);
}
}
}
permute(["A","B","C", "D"],0,3);
// sample execution //for more details refer this link
// http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/