"No repeats please" - can't understand - please help [Solved][Spoilers]

"No repeats please" - can't understand - please help [Solved][Spoilers]
0

#1

Hi,

It’s been several days that I’m stuck with this challenge. I tried to use Heap’s algorithm challenge but something seems to go wrong as my code doesn’t produce expected results (Missing some permutations ?).

function permAlone(str) {
  var  result = [], strArray = str.split(""), positionTemp;
  
  console.log ("strArray : " + strArray);
  function generate(n,strArray) {
    if (n == 1) {
      result.push(strArray.join(""));
    } else {
      for (i = 0, c = n - 1; i < c; i++) {
        generate(n - 1, strArray);
        if (n % 2 === 0){
          positionTemp = strArray[i];
          strArray[i] = strArray[n - 1];
          strArray[n - 1] = positionTemp;
          result.push(strArray.join(""));
        } else {
          positionTemp = strArray[0];
          strArray[0] = strArray[n - 1];
          strArray[n - 1] = positionTemp;
          result.push(strArray.join(""));
        }
      }
      generate(n - 1, strArray);
    }
  }
  
  generate(strArray.length,strArray);
  
  result = result.filter(function(obj){
    if (/(.)\1/g.test(obj) !== true) {
      return obj;
    }
  });
  
  
  console.log("result final : " + result);
  console.log("length result final : " + result.length);
  console.log("---------------");
  return result.length;
}

permAlone('aab');

What’s going wrong ? Could someone help me out ?


#2

Corrected a few errors.
Seems to give me twice the number of permutations - 1… so strange…

function permAlone(str) {
  var  result = [], strArray = str.split(""), positionTemp;
  
  console.log ("strArray : " + strArray);
  function generate(n,strArray) {
    if (n == 1) {
      result.push(strArray.join(""));
    } else {
      for (var i = 0; i < n - 1; i++) {
        generate(n - 1, strArray);
        if (n % 2 === 0){
          positionTemp = strArray[i];
          strArray[i] = strArray[n - 1];
          strArray[n - 1] = positionTemp;
          result.push(strArray.join(""));
        } else {
          positionTemp = strArray[0];
          strArray[0] = strArray[n - 1];
          strArray[n - 1] = positionTemp;
          result.push(strArray.join(""));
        }
      }
      generate(n - 1, strArray);  
    }
  }
  
  generate(strArray.length,strArray);
  
  console.log("length result final before filter: " + result.length);
  
  result = result.filter(function(obj){
    if (/(.)\1+/g.test(obj) !== true) {
      return obj;
    }
  });
  
  
  console.log("result final : " + result);
  console.log("length result final : " + result.length);
  console.log("---------------");
  return result.length;
}

permAlone('aab');

Anybody has a clue ?


#3

Found another bunch of errors… I’m feeling close to the goal.
Anybody can point out the remaining errors ? Console.log gives me strange ‘result’ value before regExp filtering…

function permAlone(str) {
  var  result = [], strArray = str.split(""), temp;
  
  console.log ("strArray : " + strArray);
  function generate(n,strArray) {
    if (n == 1) {
      result.push(strArray.join(""));
    } else {
      for (var i = 0; i < n - 1; i++) {
        generate(n - 1, strArray);
        if (n % 2 === 0){
          temp = strArray[n - 1].slice();
          strArray.splice(i, 1, temp);

        } else {
          temp = strArray[n - 1].slice();
          strArray.splice(0, 1, temp);

        }
      }
      generate(n - 1, strArray);  
    }
  }
  
  generate(strArray.length,strArray);
  
  console.log("length result final before filter: " + result.length);
  console.log("result final before filter: " + result);
  
  result = result.filter(function(obj){
    if (/(.)\1+/g.test(obj) !== true) {
      return obj;
    }
  });
  
  
  console.log("result final : " + result);
  console.log("length result final : " + result.length);
  console.log("---------------");
  return result.length;
}

permAlone('aab');

#4

Yay, finally found the solution by myself… :S
For those interested, I had a (stupid) problem declarating variables, swapping values and introducing temporary values in the array. Should have read Heap’s algorithm more precisely before implanting it…

Here is my final code:

function permAlone(str) {
  var  result = [], strArray = str.split(""), temp;
  
  console.log ("strArray : " + strArray);
  function generate(n,strArray) {
    if (n == 1) {
      result.push(strArray.join(""));
    } else {
      for (var i = 0; i < n - 1; i++) {
        generate(n - 1, strArray);
        if (n % 2 === 0){
          temp = strArray[i];
          strArray[i] = strArray[n - 1];
          strArray[n - 1] = temp;
        } else {
          temp = strArray[0];
          strArray[0] = strArray[n - 1];
          strArray[n - 1] = temp;
        }
      }
      generate(n - 1, strArray);  
    }
  }
  
  generate(strArray.length,strArray);
  
  console.log("length result final before filter: " + result.length);
  console.log("result final before filter: " + result);
  
  result = result.filter(function(obj){
    if (/(.)\1+/g.test(obj) !== true) {
      return obj;
    }
  });
  
  
  console.log("result final : " + result);
  console.log("length result final : " + result.length);
  console.log("---------------");
  return result.length;
}

permAlone('aab');

#5

Good work! Self solved algorithms are the best.

I haven’t done No repeats, yet.

I had a short crack at it the other day and it was melting my brain :slight_smile:


#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

I love this solution! :heart_eyes:
I have spent very long time on this problem and every solution that i have found it’s very complicated.
Can you explain to me how this work?


#8

I just finished this challenge too, using the same approach (Heap’s algorithm). I’m having a hard time understanding how the two calls to the containing function (generate(n - 1, strArray); in your case) work. Essentially, the first thing that happens in the main function is a call to itself! And that is from within a for loop. Doesn’t that interrupt the function before it does anything else? Or does it create parallel instances of the function? And then it calls itself again after exiting the loop.

I understand how the algorithm works in general but I can’t follow the variables through the function.