Heap's Algorithm_Can someone walk me through the code?

Heap's Algorithm_Can someone walk me through the code?
0.0 0

#1

Hello. I wondered if someone could walk me through the inner workings of the algorithm on Wikipedia (https://en.wikipedia.org/wiki/Heap's_algorithm). I am having difficulty seeing how it creates the patterns shown in the visual aid provided on the right side.

Thanks heaps!


#3

I hope this doesn’t break your brain the way it broke mine.


#4

I spent about four hours working out the algorithm and making the video (sooo many takes), so I hope this can help some people.


#5

This is awesome Jacey. and very well explained esp. this one involving recursions.


#6

This is perfect. This walkthrough is exactly what I was looking for. Thanks for sharing!


#7

Hello. I’m testing out my code so far and wondered why I’m getting zero for numNoRepeats instead of 1. Thanks in advance.

function permAlone(str) {
  var array = str.split('');
  var n = array.length;
  var numNoRepeats = 0;
  var newArray = [];
  var swap;
  var temp;
  var regex;
  
  swap = function(a,b){
    temp = array[a];
    array[a] = array[b];
    array[b] = temp;
  };
  
  regex = /([a-zA-Z])\1+/;
  
  function noRepeats(n, array){
    if (n === 1) {
      numNoRepeats++;
    } else {
      for (var i = 0; i < n - 1; i++) {
        noRepeats(n-1, array);
        if (n % 2) {
          swap(array[i], array[n-1]);
          newArray.push(array);
        } else {
          swap(array[0], array[n-1]);
          newArray.push(array);
        }
      }
      noRepeats(n-1, array);
    }
  }
  return numNoRepeats;
}

permAlone('b');


#8

noNumRepeats doesn’t seem to be incrementing like I would like it to. I wondered if I’m on the right track.

function permAlone(str) {
  var array = str.split('');
  var n = array.length;
  var numNoRepeats = 0;
  var newArray = [];
  var swap;
  var temp;
  var regex;
  
  swap = function(a,b){
    temp = array[a];
    array[a] = array[b];
    array[b] = temp;
  };
  
  regex = /([a-zA-Z])\1+/;
  
  function noRepeats(n){
    if (n === 1) {
      numNoRepeats++;
    } else {
      for (var i = 0; i < n - 1; i++) {
        noRepeats(n-1, array);
        if (n % 2) {
          swap(array[i], array[n-1]);
          newArray.push(array);
        } else {
          swap(array[0], array[n-1]);
          newArray.push(array);
        }
      }
      noRepeats(n-1, array);
    }
  }
  for (var j = 0; j < newArray.length; j++){
    if (!regex.test(array.join(''))) {
        numNoRepeats++;
        }
  }
  return numNoRepeats;
}

permAlone('b');

#9

You’re declaring numNoRepeats inside the function permAlone, but trying to return it outside of that function, which won’t work due to local scope.

If you want to access that variable outside of the function, you should declare it outside of the function.