Created
May 18, 2017 21:34
-
-
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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