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

问题:

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']));


回答1:

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; }

  • 发表于 2019-02-21 01:42
  • 阅读 ( 229 )
  • 分类:sof

条评论

请先 登录 后评论
不写代码的码农
小编

篇文章

作家榜 »

  1. 小编 文章
返回顶部
部分文章转自于网络,若有侵权请联系我们删除