# Heap's Algorithm never seems to work for me

Heap's Algorithm never seems to work for me
0

#1

So, I’ve tried implementing Heap’s Algorithm for the Day 4 solution of the Advent of Code, but it never seems to work correctly. I follow the algorithm to the T, and yet there’s always some sort of issue.

And have tried variations on them. Still nothing

Here’s the code that I have written. It seems to work fine up until you go beyond a string with a length of 4. After that, it starts to repeat the same combinations, and it skips other combinations that are possible

``````function heapPermutation(word) {
const wordArr = word.split('');
const perms = [];

function swap(i, j) {
const temp = wordArr[i];
wordArr[i] = wordArr[j];
wordArr[j] = temp;
}

function generate(n) {
if (n === 1) {
perms.push(wordArr.join(''));
}
else {
for (let i = 0; i < n-1; i++) {
generate(n-1);
swap(i%2 ? 0 : i, n-1);
}
generate(n-1);
}
}

generate(wordArr.length);
return perms;
}
``````

#2

For some reason Heap’s was easy task for me

Heap's spoiler
``````const isEven = x => x % 2 === 0

const swap = (arr, idx1, idx2) => {
if (isEven(idx2)) idx1 = 0
const temp = arr[idx1]
arr[idx1] = arr[idx2]
arr[idx2] = temp
};

const generatePermutations = (inputArr, callback) => {
const arr = [...inputArr];
(function generateNext(lastIdx) {
if (lastIdx === 0) callback(arr)
else {
for (let idx = 0; idx < lastIdx; idx += 1) {
generateNext(lastIdx - 1)
swap(arr, idx, lastIdx)
}
generateNext(lastIdx - 1)
}
}(arr.length - 1))
}

let result = []
generatePermutations('abcdef', x => { result = [...result, x.join('')] })
``````

Indtead of this F# code, which I failed to implement in js:

F# permutations in 6 lines:
``````    // From: http://stackoverflow.com/questions/286427/calculating-permutations-in-f
// Much faster than anything else I've tested

let rec insertions x = function
| []             -> [[x]]
| (y :: ys) as l -> (x::l)::(List.map (fun x -> y::x) (insertions x ys))

let rec permutations = function
| []      -> seq [ [] ]
| x :: xs -> Seq.concat (Seq.map (insertions x) (permutations xs))
``````

upd: FOUND TEH SOLUTION!

It's ... beautiful
``````const insertions = (x, [y, ...ys]) =>
!y ? [[x]] :
[[x, y, ...ys], ...insertions(x, ys).map(zs => [y, ...zs])]

const permutations = ([x, ...xs]) =>
!x ? [[]] :
[].concat(...permutations(xs).map(ys => insertions(x, ys)))
``````