The "No Repeats Please" Challenge

The "No Repeats Please" Challenge
0

#1

I think I’m not understanding the goal of this challenge.

It says find all the permutations without repeating characters.
To me, the number of permutations with repeating characters in these examples
should be fairly small- for example, for the example ‘abcdefa’, assuming a1 and a2 are unique, it seems like there only 12 positions “aa” can appear. Based on that I want the answer to be 7! - 12. Obviously, that ain’t it. what am I missing?
I’m looking at read-search-ask and it isn’t helping.


#3

Yeah, there are only 12 positions where aa can appear, but for each position you also have to take account the permutations of the other letters.

Suppose aabcdef. This permutation will appear twice (this, and if you swapped the two a's), but then there’s also aabcdfe, aabcfde, aabfcde, etc (not to mention their doubles). I don’t know the answer though, but it’s obviously not just 7! - 12.

EDIT: Oh someone has answered :slight_smile:


#4

I see what I was missing now. There are only 12 positions “aa” can be in but many more position the other characters can be in around the “aa”. That’s the insight I was missing.

I also tried to just figure out a formula and I found the 7-(6!)2 which also worked with the first example ( 3! - (2!)2 ) but I couldn’t figure out how to apply it to the example that had double “a” and “f”.


#6

@P1xt Thank you for your answer,. I also came as far as @shamieya with the formula (7!)-(6!)2. Could you explain the answer? I just don’t get the 4 It must have something to do with the doubles I guess, but how?


#8

@P1xt Thank you so much for your extensive answer. I won’t try to deduce the formula then, I think it will take way too much time with no insurance of succes. And I promise I will not peak at your code (yet), but try to figure it out myself first.
Thanks again!


#10

I’ve recently spent a whole day on this challenge, trying to come up with a mathematical solution to this.
Since this is a numerical problem I didn’t think we are expected to use the brute force way. But the math behind it is very hard for me.

Most solution I’ve come across in my looking around were indeed variations on the brute force solution some of them did abort earlier and there were some performance enhancing datastructure in use. Most of them still collapsed with string lengths > 10

I’ve come across a very good explanation on stackoverflow where the soltions for arbitrary amounts of double letters is spelled out.

I tried that and also fiddled with solving repeating chars > 2 using a recursion. Which is when my testcases went green and I passed the challenge.

I didn’t believe that my blind attempts were successful so I calculated some more numbers from other strings using other peroples solutions. My function produces different results in many case thus I believe my code is wrong. Yet my tests are passing. Thats why I opened an issue on github because I want more testcases

Issue: Challenges/no-repeats-please needs more tests

If any of you fine folks have a working numerical solution to this problem I’d be very interested in it!


#12

I did it the straightforward way. This was inspired by @P1xt’s one. First I did it with Heap’s algorithm, but did not get how the algorithm works.

function permAlone(str) {
  var arr = str.split("");
  var reg = /(.)\1+/; //regexp for repeating characters
  var perms = 0;
  //recursive function swaps elements of an array from indexFrom position to indexTo position
  //and then proceeds to do so starting from indexTo+1 position and so on till the end of an array is reached
  function swap(indexFrom, indexTo, arr) {
    //check if the position is last, meaning we have reached the end of the array(permutation instance)
    if (indexTo==arr.length-1) {
      var enterStr = arr.join("");
      if (!reg.test(enterStr))
      perms++;} // increment counter if no repeats
    else {
    var newArr = [];//newArr(copy of arr) is needed so that not to modify the original one, as next calls of swap() need it
    for (var i=0; i<arr.length; i++) {
      newArr.push(arr[i]);
    }
    var temp = newArr[indexFrom];
    newArr[indexFrom] = newArr[indexTo];
    newArr[indexTo] = temp;
    
    for (i =indexTo+1; i< arr.length; i++)
     {
      swap(i,indexTo+1, newArr);
     }
   }
  }
//start recursion
    for (var i =0; i< arr.length; i++)
     {
        swap(i,0, arr);
       }
       
  return perms;
}

`

#13

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

#14

Your code works perfectly, but I can’t understand what you’ve done there.
I’m a newbie here.

Please can you try explaining some bits of your code.

Thanks.


#15

I’ve tried to “un-golf” jjames’ code. Maybe this is more readable to you. Reading nested ternary operators makes me want to slap people.

function permAlone(str, p) {
    return str.split('').reduce(function(result, element, index) {
        if (element == p) {
            return result;
        } else {
            if (str.length == 1) {
                return 1;
            } else {
                return result + permAlone(str.slice(0, index) + str.slice(index + 1), element);
            }
        }
    }, 0);
}

#16

Ya, thanks for that. It’s pretty much better.


#18

@P1xt, I got your point. I’m just a beginner and always get excited at short code (or at least shorter code than mine). I’ve not chosen that code as my solution; I already got the solution but wanted to understand what exactly @jjames did there. My code works pretty well though it’s the brutal force approach.

On a different note, one can figure out that freecodecamp expects the use of Regex (they gave that as a clue); which I guess will definitely land one the same brutal force approach.


#19

Hi @P1xt, I’m sorry you were bothered by the example code I posted, I agree it isn’t optimally understandable by itself, but it really isnt meant to be understood on it’s own. That’s why I wrote the paragraphs before it. Those were kind of the main idea of the post, the actual example code was just extra, just one implementation of those two ideas. It also was not aimed at folks with a beginner’s knowledge of JavaScript, it is in the advanced section after all! I think you may have overlooked the main idea and focused a little too much on the admittedly lazy syntax I wrote that example with.

Here’s a quick little test I just did https://www.repl.it/Cx3H/1

These are the results in milliseconds of 10 tests run in a row on my computer, based on the example tests provided by freecodecamp. The first column is the performance of the algorithm I posted, the second is yours, and the third is the one someone else posted inspired by your solution.

7.970000000000027 74.94000000000028 38.674999999999955
5.169999999999618 56.67499999999973 37.445000000000164
4.789999999999964 56.345000000000255 36.004999999999654
4.604999999999563 54.914999999999964 35.50500000000011
4.954999999999927 55.0300000000002 36.15000000000009
4.5 60.215000000000146 36.73499999999967
4.724999999999909 55.04500000000053 37.23000000000002
5.045000000000073 54.934999999999945 35.95000000000027
4.550000000000182 55.26000000000022 35.625
4.875000000000455 55.279999999999745 36.25999999999976

The method I suggested tends to run a little more than 10 times as fast as yours, and slightly less than 10 times as fast as the other solution, when executing each of the tests from this site.

Now consider one specific case that this site tests, the string “zzzzzzzz”. These are the results for the three algorithms.

0.10500000000001819 51.870000000000005 28.93999999999997
0.025000000000005684 59.014999999999986 50.91999999999999
0.029999999999972715 75.84000000000003 37.39000000000004
0.03000000000002956 40.85499999999996 35.55500000000001
0.019999999999924967 40.115000000000066 35.60500000000002
0.15499999999997272 40.229999999999905 36.88499999999988
0.1449999999999818 39.635000000000105 36.81000000000006
0.020000000000095497 40.625 35.60500000000002
0.014999999999986358 40.16500000000008 35.504999999999995
0.01999999999998181 40.98500000000013 36.335000000000036

Mine is a couple thousand times faster. This is the type of example I was trying to point out that your algorithm fails miserably at.

Also I’d like to point out that my algorithm has a memory advantage, in that it does not store any strings, instead keeping a numeric count of possible strings, whereas the type of algorithm you are claiming to prefer stores thousands of strings with an example input over 6 characters.

If you don’t understand the code, I would be more than happy to explain it to you. But dismissing it as a “marginal improvement” or not “markedly better” seems more like a gut reaction of yours than something you actually took the time to understand or to even just test yourself, and that isn’t helpful to anyone.


#21

I had completed this challenge yesterday and now I want to share my solution. My code is not short and it takes about 20 seconds to pass the tests, but on the positive side it’s quite easy to understand its logic.

I tried to make the description of my method as full as possible, so read it carefully if you still haven’t completed this challenge. I also attached my code under the spoiler at the end.

So at first I tried to figure out or google for a formula of calculating number of permutations, but failed. OK, I thought, then I need to generate them. But how? No idea. OK, let’s generate combinations and then somehow filter permutations out of them. But I still had no idea how to do it.

And then I imagined a safe, which has digits from 0 to 9 on its buttons and a 10-digit combination to open it. The number of possible combinations is easy to calculate – just raise number of buttons to the power of combination lengts: 10^10 = 10.000.000.000. Then if we want to generate all the combinations, it will start from all zeros and end with all nines. So basically we start from zero, increment it by one each time and add some zeros to the left side to make required length of combination.

0000000000
0000000001
0000000002

9999999999

At this point it started looking familiar to me. And I had added some square brackets:

[0][1][2][3][4][5][6][7][8][9]

Aren’t these indicies? Let’s add some letters.

string: a  b  c  d  e  f  g  h  i  j
index: [0][1][2][3][4][5][6][7][8][9]

[0][0][0][0][0][0][0][0][0][0]
 a  a  a  a  a  a  a  a  a  a
[0][0][0][0][0][0][0][0][0][1]
 a  a  a  a  a  a  a  a  a  b
[0][0][0][0][0][0][0][0][0][2]
 a  a  a  a  a  a  a  a  a  c

Yay! It works! But what if we have combination of not 10, but say 4 characters (0123)?

0000
0001
0002
0003

We don’t have a 4 in our arsenal, so the we should increment previous symbol, and the next values will be:

0010
0011
0012
0013
0020
0021

Doesn’t it look familiar again? It’s still our indicies, but it’s also a quaternary numeral system. And if we had a string of two characters (like “ab”), that would be a binary numeral system.

Now we need to somehow convert out habitual decimal system to whatever system we need (based on a length of input string). If you google for it, you’ll easily find out that it’s not a problem at all. Let’s say you need to convert number 26 to quaternary system.

Divide 26 by the 4 (4 represents quaternary system):
26 / 4 = 6 (whole number) and reimainder is 2. Divide your result by 4 again:
6 / 4 = 1 (whole number) and remainder is 2. Divide last time and you’ll get remainder = 1. Then put all of remainders together and you’ll get 221. The picture below may help to understand it better:

Now we need to look at our result from right to left, or in another words – reverse it: 221 --> 122. That’s our final result, 27 in decimal system will be 221 in quaternary system. Remember, that out string length is 4, so we need to add one zero to the left: 0221. Now that’s your indicies. And if your string at input was “abcd”, then 27-th combination will be “accb”:

 a  b  c  d
[0][1][2][3]

[0][2][2][1]
 a  c  c  b

So the whole algorithm for our function will be:

  1. Generate regular numbers starting from zero (which is just increment function);
  2. Convert our number to a numeral system we need (which is our input string’s length);
  3. Add zeros to the left until we get proper length (which is also our input string’s length);
  4. Split numbers we’ve got to make an array, which elements will serve as indicies for our string. At this point I also use a check for repeated consecutive indicies, cause they will make repeated consecutive letters.
  5. Use indicies we’ve got to generate an array of letters out of our string. Check for repeated consecutive letters. If they are – go to step #1 and generate our next number, if they aren’t – increase our permutations counter, then go to step #1 and generate our next number.

And we do it until we reach maximum number of possible combinations which is calculated as x^x, where x is our string’s length.

My code is here
// noprotect

function convNumSys(val, sys) {
  var newNum = [];
  
  if (val === 0) {
    return false;
  }
  
  while (val > 0) {
    newNum.push(val % sys);
    val = (val - val % sys) / sys;
  }
  newNum = newNum.reverse();
  
  while (newNum.length < sys) {
    newNum.unshift(0);
  }
  
  var repeated = isRepeatNumber(newNum);
  if (repeated === true) {
    return false;
  } else {
    return newNum;
  }
}


function isRepeatNumber(arr) {
  for (var b = 0; b < arr.length - 1; b++) {
    if (arr.join("").split(arr[b]).length > 2) {
      return true;
    }
  }
  return false;
}

function isRepeatLetter(arr) {
  for (var a = 0; a < arr.length - 1; a++) {
    if (arr[a] === arr[a + 1]) {
      return true;
    }
  }
  return false;
}


function permAlone(str) {
  var totalCycles = Math.pow(str.length, str.length);
  var currentCycle = 0;
  var permCounter = 0;
  
  if (str.length === 1) { //special case
    return 1;
  }
  
  while (currentCycle < totalCycles) {
    var indexes = convNumSys(currentCycle, str.length);
    if (indexes === false) {
      currentCycle += 1;      
    } else {
      var lettersArr = [];
      for (var b = 0; b < indexes.length; b++) {
        lettersArr.push(str[indexes[b]]);
      }
      if ( isRepeatLetter(lettersArr)) {
        currentCycle += 1;
      } else {
        currentCycle += 1;
        permCounter += 1;
      }
    }
    
  }
  
  return permCounter;
}

permAlone('abfdefa');

#22

Hi everybody,

I am trying to implement the solution based on this stackoverflow answer. The solution pass all the test expect for the two last tests. Could you put me on the right track to understand where the issue come from ? Thanks in advance.

Edit : Never mind. I read the stackoverflow answer’s comments and there was a hint of for this specific solution.

I enjoyed solving these algorithms challenges. Did you ?


#23

This was one of the hardest algorithms I had to do. I ended up referring to an algorithm book and tweaked from it to make it work. I knew I had to use recursion but didn’t know how to set it up just right. Here’s what it ended up,

function permAlone(str) {
var len = str.length;
var result = 0;
var prev = arguments[1];

 if (len === 0) { // base case
     return 1;
 }

 for (var i = 0; i < len; i++) {
     var before = str.substring(0, i);
     var after = str.substring(i + 1, len);
     var c = str.charAt(i);
     if (c == prev) continue;

     result += permAlone(before + after, c);
 }

 return result;

}

permAlone(‘aab’);


#24

Why have you used let here? Won’t it work with var?


#25

This has been the most difficult challenge so far. Based on what i’'m reading above, I did the same solution that others did.

Step 1: Try to come up with a formula for figuring out the # of perms with duplicates.
Step 2: Realize i’m not mathy enough to figure that out
Step 3: Brute force it. Generate all perms, then go through each perm and see if there’s any duplicate consecutive letters.
Step 4: Think to myself: Wow, this is not pretty and could be more efficient. But generating perms is O(N!), so why bother?
Step 5: Celebrate by posting on the forum


#26

Hahah precisely! I think everyone went through those phases and wasted time on fail maths first :smiley:


#27

Ha,ha. I’ve just done step 2.