Skip to content

Instantly share code, notes, and snippets.

@azurite
Created May 18, 2017 21:34
Show Gist options
  • Save azurite/da44a7dcd49ea0188a7bd01fce2142bb to your computer and use it in GitHub Desktop.
Save azurite/da44a7dcd49ea0188a7bd01fce2142bb to your computer and use it in GitHub Desktop.
Computes all n! permutations of an array with n items provided n < 13
/**
* Returns an array of all possible permutations of the given array provided the arrays length is smaller then 13
* @param {Array} arr The given array to compute it's permutations. Empty array if not specified.
* @returns {Array} an array of all the possible permutations of arr
*/
function perm(arr = []) {
if(arr.length > 12) {
// Javascript Array max length is 2^32 - 1 but 13! > 2^32 -1
throw new RangeError("perm() allowed max array length is 12");
}
if(arr.length <= 1) {
return [arr]; // only one permutation possible
}
else {
var lastItem = arr[arr.length - 1];
var subPerms = perm(arr.slice(0, -1)); // get all permutation of n - 1 items
var perms = [];
subPerms.forEach((subPerm) => {
var res_idx = 0, result = [], temp, descending = subPerm.length % 2 !== 0;
var arr_idx = descending ? subPerm.length : 0;
do {
temp = subPerm.slice(0);
temp.splice(arr_idx, 0, lastItem); // place the n-th item at each possible index for each (n - 1)-th permutation
result[res_idx++] = temp;
} while (descending ? arr_idx-- : arr_idx++ < subPerm.length);
perms.push.apply(perms, result);
});
}
return perms;
}
// If the file is run from the console via "node perm.js <str>" the <str> must be a JSON string that can be parsed into an array
// for example: "node perm.js '[1,2,3,4]'" will give you all permutations of the array [1,2,3,4]
// otherwise you can just require() the function as a module like so: "var perm = require('./perm.js')"
if(require.main === module) {
var data;
try {
data = JSON.parse(process.argv[2]);
}
catch(e) {
console.error("Argument cannot be parsed by JSON.parse");
console.error("Reason: " + e.message);
process.exit(1);
}
console.log("Permutations of ", data, ":");
console.log(perm(data));
}
else {
module.exports = perm;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment