heap's algorithm - JavaScript

Question

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

Nina Scholz · Accepted Answer · 2019-02-19 21:52:27Z

6

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

answered Feb 19, 2019 at 21:52

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

totalnoob Over a year ago

what's happening when I push the array vs when I push a copy of the array?

Nina Scholz Over a year ago

if you push the array, you have an array of same object references to the same array. by taking a copy with slice, you get independent new arrays.

Timothy Jones Jul 10 at 17:29

This code -- the myCall function -- shows how you can preserve each permutation and then do whatever do it. Its stored as a string here, but that can be converted into an array easily.

Timothy Jones · Accepted Answer · 2025-07-09 11:09:49Z

-1

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
    <title>Heap's Algorithm</title>
<script>
function swap(array, pos1, pos2)
{
  var temp = array[pos1];
  array[pos1] = array[pos2];
  array[pos2] = temp;
}
var myString;
function heapsPermute(array, n)
{
  n = n || array.length;
  results = []; 
  if (n === 1) {
    results.push(array);
    myString += array.join('').toString();
  } else {
    for (var i = 1; i <= n; i++) {  //i = i+1
      heapsPermute(array, n - 1);  //deleting , results
      if (n % 2) {
        var j = 1;
      } else {
        var j = i;
      }
      swap(array, j - 1, n - 1);
    }
  }
  return results;
}
var myArray = new Array(1,2,3,4); // = [1,2,3];
var myArraySize = myArray.length;
heapsPermute(myArray);
myString2 = myString.replace("undefined", "");
function myCall()
{
    for(var i=0; i < myString2.length/myArraySize; i++)
        document.myForm.myTextArea.value += i + ' ' +myString2.slice(myArraySize*i,myArraySize*(i+1)) + '\n';
}
</script>   

</head>

<body>
<form name="myForm">
<input type="button" value="Test" onClick="myCall();">
<textarea cols="10" rows="10" name="myTextArea" id="myTextArea"></textarea>
</form>
</body>
</html>

answered Jul 9 at 11:09

Timothy Jones

11

3 Comments

Timothy Jones Jul 9 at 11:14

This doesn't require the console and works as an html page in Homesite and other html editors.

Community Jul 9 at 11:14

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.

Timothy Jones Jul 10 at 17:30

This saves the permutations into a string that can be parsed later.

Collectives™ on Stack Overflow

heap's algorithm - JavaScript

2 Answers 2

3 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related