No repeats please, Heap's algorithm and frustration with recursions

No repeats please, Heap's algorithm and frustration with recursions
0.0 0

#1

This frustrates me so much, even though I understand basic principles of recursion. When it comes to applying it to solving complicated algorithms I just can’t figure out how to take advantage of it. It frustrates me so much, it just makes me want to quit(that’s not going to happen don’t worry) it makes me feel I am not wired for understanding such a complicated things and it gives me the worst feeling ever that I am just not smart enough for this profession.

I am trying to solve no repeat please algorithm and it requires recursion. I kind of know what I need to do to solve it but I just can’t pull off the code. It is so bad I can’t even figure out how other people’s code work. There are so many things going on simultaneously that I just lose the track of it. It causes so much confusion for me.

Here is the link to algorithm No-repeats-please:

So I know I need to write function that will give me an array of all permutations of the string
And my mathematical idea of how to do it is described in this video so I understand how to break down permutation process.

Then I filter the array with the regex expression that looks for repeated characters in an array of strings.
Sounds easy but it is not.
I got no idea how to write the code that follows this process of permutation and I it is destroying me. Please help me somehow.


#2

It’s okay to be frustrated. This isn’t a way of thinking or problem solving that is familiar to most of us. It seems to me that recursion is one of those things that a lot of people have to be introduced to a couple times before they “get it” (and we usually still think we’re pretty bad at it).

While recursion is an important principle to become familiar with, remember that it’s not the end-all-be-all. There’s a number of reasons why it might not be the best idea in a given situation. Anything that can be done with loops can be done recursively and anything that can be done recursively can be done with loops. Sometimes there’s no meaningful difference and other times one approach can replace horribly complex logic with something much more simple.

“No repeats please” is a hard challenge. Solve it whatever way you can first, then come back and refactor. Give yourself a break when you need to.

“Sounds easy but it is not” is pretty much the story of regex. Just keep swimming. :tropical_fish: Come back with fresh eyes every now and then.


#3

@ArielLeslie Thank you.


#5

Thank you so much. This was a huge obstacle for me I finally overcome it. There were too many things going on simultaneously so I would get overwhelmed. It took me almost 2 weeks to get this challenge done and understand it. I work full time so I can’t afford to code more than 1 hour a day.
I solved the problem with recursion but one thing that really helped me conceptually understand what’s going on in this algorithm was rewriting the code in the double loop for 3 letters string.

It is also very important to understand the algorithm first, I was confused with replacing same letters like A with A and B with B in first two iterations because it made swapping letter back to the state from earlier iteration confusing it seems like you are swapping same letter back and forth without achieving anything. This is the illustration that helped me understand it. And this video helped a lot even though the code in the video is in python

Here is my final code:

function permAlone(str) {

  // Create a regex to match repeated consecutive characters.
  var regex = /(.)\1+/g;

  // Split the string into an array of characters.
  var arr = str.split('');
  var permutations = [];
  var tmp;

 

  //Generate arrays of permutations using the algorithm.
  function generate(arr, start, end) {
    var current = 0;
    if (start === end-1) {
      // Make sure to join the characters as we create  the permutation arrays
      permutations.push(arr.join(''));
    } else {
      for (current = start; current < end; current++) {
        tmp = arr[start];
        arr[start] = arr[current];
        arr[current] = tmp;
        generate(arr, start+1, arr.length);
        tmp = arr[start];
        arr[start] = arr[current];
        arr[current] = tmp;
      }
    }
  }

  generate(arr, 0 ,arr.length);

  // Filter the array of repeated permutations.
  var filtered = permutations.filter(function(string) {
    return !string.match(regex);
  });

  //Return how many have no repetitions.
  return filtered.length;
}

Here is the code for a permutation of the array with 3 elements without using recusrsion. This was really helpful step back from recursion that helped me understand the purpose of the recursion for this algorithm and hopefully it will help some of the new programmers like me to conceptually understand the algorithm :

var testArr = ["a", "b", "c"];
function generate(arr, start, end) {
  //loop through array
  for(var i = 0; i<end; i++){
    // start is 0 because we want to swap charachter on position 0
    start=0;
    // swap char 0 with char i
    var temp = arr[start];
    arr[start] = arr[i];
    arr[i] = temp;
    //loop throug array and skip char 0
    for(var j=1; j<end; j++){
      // start = 1 because we want to swap charachter on position 1
      start = 1;
      temp = arr[start];
      arr[start] = arr[j];
      arr[j] = temp;
      //print out arr after char 1 is swaped
      console.log(arr);
      // reverse char 1 one step back
      temp = arr[start];
      arr[start] = arr[j];
      arr[j] = temp;
    }
    //reverse char 0 one step back
    start = 0;
    temp = arr[start];
    arr[start] = arr[i];
    arr[i] = temp;
  }

}
generate(testArr, 0, testArr.length );

#6

I really liked this one, and everyone seems to miss two very big ideas when they solve this algorithmically, so im cross posting this to a few of these threads.

1. When you are forming each permutation, and you come across one that has repeating letters, you do not need to keep going.

this is the difference between only going through a handful of steps to solve the test case ‘aaaaaaaa’, or finding 40320 permutations just to filter every single one out afterwards.

2. You are asked to return a number, not a list. Storing an array of thousands of strings is unnecessary.

You dont actually need the list of strings, you just need to keep track of how many you find. This is only possible when you keep (1) in mind.

You can think of the problem in this way:

How many unique routes can I take through a string, without passing through identical letters consecutively?

Then you can set up a much simpler algorithm to traverse the letters of a string and count how many times it can successfully get through the entire string without hitting the same letter twice.

This is one possible solution using these two ideas:

function permAlone(s,p){

  return s.split('').reduce(
    (x,y,i)=> y==p ? x : s.length==1? 1 : x + permAlone(s.slice(0,i) + s.slice(i+1),y) ,0);
  
}


#7

thank you, it is awesome to see different perspectives and more advanced code


#8

This is a nice solution.


#9

Whenever using recursion just check that it works for two consecutive times correctly.

It becomes complicated for people to imagine how their code will work when using recursion because they fall in the loop of recursion themselves . Just have faith that if it works for two consecutive loops , it will work for any no. of loops. Much like the principle of mathematical induction or the DOMINO effect .

Hope this helps you simplify the idea of recursion .


#10

@jjames - Your permAlone has two parameters s and p. What is p supposed to represent? The only value passed to the function is a string. I am missing something.


#11

@rmdawson71 When the function is first called the only value passed is a string, but it is recursive and each time it is called thereafter it is passed a string (s) and the previous letter examined (p. This is to avoid counting strings that repeat letters


#12

I see now. Somehow I missed it the first time.