CODEWITHSUNDEEP
javascriptheaps-algorithm
totalnoob
totalnoob

Reputation: 2741

heap's algorithm - JavaScript

I have an alright understanding of how Heap's Algorithm works, but I can't figure out how to add each unique permutation into an array and return it based on the recursive nature of the algo.

why is it only adding the same permutation but the console log prints out the different ones?

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

var heapsPermute = function (array, n, results = []) {
  n = n || array.length;
  if (n === 1) {
    results.push(array);
    console.log(array);
  } else {
    for (var i = 1; i <= n; i += 1) {
      heapsPermute(array, n - 1, results);
      if (n % 2) {
        var j = 1;
      } else {
        var j = i;
      }
      swap(array, j - 1, n - 1);
    }
  }

  return results;
};

console.log(heapsPermute(['a', 'b', 'c', 'd']));

Upvotes: 3

Views: 955

Answers (1)

Nina Scholz
Nina Scholz

Reputation: 386766

You need to add a copy of the array, instead of the array and it's object reference.

results.push(array.slice());
//                ^^^^^^^^


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

var heapsPermute = function (array, n, results = []) {
  n = n || array.length;
  if (n === 1) {
    results.push(array.slice());
  } else {
    for (var i = 1; i <= n; i += 1) {
      heapsPermute(array, n - 1, results);
      if (n % 2) {
        var j = 1;
      } else {
        var j = i;
      }
      swap(array, j - 1, n - 1);
    }
  }
  return results;
};

console.log(heapsPermute(['a', 'b', 'c', 'd']).map(a => a.join(' ')));
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 5

Related Questions