# Heap's Algorithm

``````var swap = function (array, pos1, pos2) {
var temp = array[pos1];
array[pos1] = array[pos2];
array[pos2] = temp;
};

var heapsPermute = function (array, output, n) {
n = n || array.length; // set n default to array.length
if (n === 1) {
output(array);
} else {
for (var i = 1; i <= n; i += 1) {
heapsPermute(array, output, n - 1);
if (n % 2) {
var j = 1;
} else {
var j = i;
}
swap(array, j - 1, n - 1); // -1 to account for javascript zero-indexing
}
}
};

// For testing:
var print = function(input){
console.log(input);
}

heapsPermute(['a', 'b', 'c', 'd'], print);
``````

``````[ 'a', 'b', 'c', 'd' ]
[ 'b', 'a', 'c', 'd' ]
[ 'c', 'a', 'b', 'd' ]
[ 'a', 'c', 'b', 'd' ]
[ 'b', 'c', 'a', 'd' ]
etc...
``````

I was wondering if anyone could tell me a way to modify this algorithm so that it gives every permutation of length n from an array of letters.
For example if n is 2:

``````['a', 'b']
['a', 'c']
['a', 'd']
etc...
``````

Thank you for taking the time to read my question. Any help much appreciated.

This is the technical definition of a heap’s algo according to this repo of algos https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/permutations

A permutation, also called an “arrangement number” or “order”, is a rearrangement of the elements of an ordered list `S` into a one-to-one correspondence with `S` itself

Therefore I don’t think what you ask can be solved with this algorithm, since it needs to have a one-to-one correspondence (same size). Unless what you are looking for is to just splice a portion of the results so that

``````[ 'a', 'b', 'c', 'd' ]
[ 'b', 'a', 'c', 'd' ]
[ 'c', 'a', 'b', 'd' ]
[ 'a', 'c', 'b', 'd' ]
[ 'b', 'c', 'a', 'd' ]
etc...

// becomes
[ 'a', 'b' ]
[ 'c', 'd' ]
[ 'b', 'a' ]
[ 'c', 'd' ]
[ 'c', 'a' ]
[ 'b', 'd' ]
[ 'a', 'c' ]
[ 'b', 'd' ]
[ 'b', 'c' ]
[ 'a', 'd' ]
etc...
``````
1 Like

OK, just curious. Is there any reason that your solution must use Heap’s or do you just need a solution that gives that result?

You could probably come up with some way to pare down the array to length = n many times and feed those pared down arrays to your Heap’s function but there are easier ways to calculate those results.

[ ‘a’, ‘b’, ‘c’, ‘d’ ]
[ ‘b’, ‘a’, ‘c’, ‘d’ ]
[ ‘c’, ‘a’, ‘b’, ‘d’ ]
[ ‘a’, ‘c’, ‘b’, ‘d’ ]
[ ‘b’, ‘c’, ‘a’, ‘d’ ]
etc…

// becomes
[ ‘a’, ‘b’ ]
[ ‘c’, ‘d’ ]
[ ‘b’, ‘a’ ]
[ ‘c’, ‘d’ ]
[ ‘c’, ‘a’ ]
[ ‘b’, ‘d’ ]
[ ‘a’, ‘c’ ]
[ ‘b’, ‘d’ ]
[ ‘b’, ‘c’ ]
[ ‘a’, ‘d’ ]
etc…

OK - not sure if this is faithful to Heap’s algorithm but I believe it does what you are asking.

``````// calculate permutations of elements in an array
// params
// arr - arr of items to permutate
// [len] - optional length of permutation if less than arr.length
// [repeat] optional allow repeat use of array items defaults to false

function permutations(arr, len, repeat = false) {

len = len || arr.length;
if(len > arr.length) len = arr.length;
const results = [];

function eliminate(el, arr) {
let i = arr.indexOf(el);
arr.splice(i, 1);
return arr;
}

function perms(arr, len, prefix = []) {
if (prefix.length === len) {
results.push(prefix);
} else {
for (let elem of arr) {
let newPrefix = [...prefix];
newPrefix.push(elem);

let newRest = null;

if(repeat){
newRest = arr;
}else{
newRest = eliminate(elem, [...arr]);
}

perms(newRest, len, newPrefix);
}
}
return;
}
perms(arr, len);

return results;
}

// using all places, no repeats as expected with Heap's
console.log(permutations(['a', 'b', 'c', 'd', 'e']).length);

// limited to 3 places, no repeat use of elements
console.log(permutations(['a', 'b', 'c', 'd', 'e'],3).length);

// limited to 3 places, allowing repeat use of elements
console.log(permutations(['a', 'b', 'c', 'd', 'e'],3, true).length);
``````

Hi there alhazen1. I apologize for my untimely response. Thank you for your solution. It seems to work very well. I shall study it further later on today. It being faithful to Heap’s or not is not important. I should have clarified that in my original post. Thank you again for your help.