Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Generate all permutations of an array. Alternative to the many variants of heap's algorithm I keep finding on the interweb. Every single algorithm I found produced incorrect results. This one is correct.
/**
* This variant takes a max depth as the second argument.
*/
const permutations = (value, max = value.length) => {
let depth = Math.min(max, value.length);
let results = [];
const permute = (queue = []) => {
if (queue.length === depth) {
results.push(queue);
} else {
for (let ele of value) {
permute(queue.concat(ele));
}
}
};
permute();
return results;
};
console.log(permutations(['a', 'b', 'c', 'd', 'e']).length); // 3125
console.log(permutations(['a', 'b', 'c', 'd', 'e'], 4).length); // 625
console.log(permutations(['a', 'b', 'c', 'd', 'e'], 3).length); // 125
console.log(permutations(['a', 'b', 'c', 'd', 'e'], 2).length); // 25
console.log(permutations(['a', 'b', 'c', 'd', 'e'], 1).length); // 5
/**
* This variant takes a transform function to modify each set
* before it's pushed onto the results array
*/
const identity = ele => ele;
const permutations = (arr, max = arr.length, fn = identity) => {
if (typeof max === 'function') return permutations(arr, arr.length, max);
let depth = Math.min(max, arr.length);
let results = [];
const permute = (queue = []) => {
if (queue.length === depth) {
results.push(fn(queue));
} else {
for (let ele of arr) {
permute(queue.concat(ele));
}
}
};
permute();
return results;
};
console.log(permutations(['a', 'b', 'c'], 2, ele => ele.join('.')));
/**
* Generates all permutations of an array, including duplicate
* character sequences, like "aaa", "aab", and so on.
*/
const permutations = (array = []) => {
let len = array.length;
let results = [];
const permute = (queue = []) => {
if (queue.length === len) {
results.push(queue);
} else {
for (let ele of array) {
permute(queue.concat(ele));
}
}
};
permute();
return results;
};
console.log(permutations(['a', 'b', 'c', 'd', 'e']).length); // 3125
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment