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.

I looked through these links:

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)))