The Latest

Free Code Camp: No Repeats Please

Reading Time: 2 minutes

I’m not gonna lie, I had a hell of a time with No Repeats Please and I’m not alone ( see the unfortunately closed github issue). This one isn’t easy. It isn’t intuitive. The math doesn’t match up to my understanding of how to calculate permutations. However, it can be done.

To everyone who hasn’t started it yet, here’s a few tips to get you on the right footing.

Empty Your Mind

First and foremost, forget the link to the permutations article in the exercise. It will be of no help at all. I spend about 3 days trying to understand how “aab” was 2 and “aabb” was 8 using your normal permutations with no repeats functions. It doesn’t work. It won’t work. It can’t work.

I then thought I might be on the right path with this helpful post at Math.stackexchange. However, though I understood the example they showed, I still couldn’t apply it to the numbers FCC was testing against.

Consider:

AAABBBCCC

\dfrac{9!}{3!\times 3!\times 3!}-( \,3\times\dfrac{7!}{3!\times 3!}) \,+( \,3\times\dfrac{5!}{3!}) \,-3!= 1314

So aabb should be:

\dfrac{4!}{2!\times 2!}-( \,2\times\dfrac{3!}{2!}) \,+( \,2\times2!) \,-2!= 2

The permutations in which no letter is repeated consecutively being abab and baba.

So just drop that. It won’t do you any good.

A New Tack

Instead, the route to take seems to be to generate ALL of the possible combinations and then filter out the ones that have repeating consecutive characters, as is suggested in this Reddit post from a similarly frustrated camper.

To do this, most folks went to Heap’s algorithm, which is an algorithm for generating all possible permutations of a number of objects. Note here that it isn’t enough to simple calculate all of the possible permutations using a factorial function (believe me, I tried). You need to actually generate the permutations, so that you can compare the characters.

The Wikipedia article uses Java-like psuedocode. You can see a couple of variations in Javascript in this code review on Stack Exchange.

Next Steps

Once you’ve got an array holding all of the possible permutations of the input string, then the next step is to filter out the array elements that have repeated consecutive characters. To do this, test each element against a regex string. You can use the Array.filter method to perform this test and then save the resulting array to a variable. Here’s how mine looked:

//If there are repeated characters, strip out of the array
 var filtered = permutations.filter(function(string) {
 return !string.match(regex);
 });

Last but not least, return the length of the this new filtered array, to get your final answer.

Easy, huh? NOT!!!!

But I sincerely hope that this will save someone else a couple days of headaches.

3 Comments

  1. August 30, 2016 - Reply

    So I’m working on this problem right now and have been banging my head on the math side for quite a while. I might be making progress, but I felt like some googling was in order to see what tacks others had used and I found your article. Using a recursive generating function was my first thought actually. Good ‘ol brute force technique. However, upon my first implementation that seemed sound I immediately ran into a lack of processing power! I figured, “they can’t expect me to have a powerful computer to complete just a challenge” and went back to the math route.

    Did I just mess up something, or is this a fairly CPU intensive route even done correctly? I also didn’t try the non-recursive Heap’s algorithm, so that could prove the route to go. I’m just interested in your thoughts before I completely abandon my sweet, sweet math.

    • August 30, 2016

      Hi Eli,
      Abandon all math, those who enter here! I don’t think that this problem can be solved mathematically. You have to generate all possibilities and filter.

      After all the time I spent calculating permutations on the back of any spare paper I could get my hands on, I went right to Heap’s algorithm after I found it, so I can’t speak to a recursive solution. If you’re getting a stack overflow issue or “too much recursion”, though, that’s probably a problem somewhere with your solution. I reckon it’s possible to do recursively, if you want to stick with that idea. You might even be able to take the algorithm pseudocode and translate that into recursion.

      Hope that helps!

    • Mihai Manole
      September 18, 2017

      Look at my Advanced Code Solution on https://gist.github.com/mesterum/0e7adf9826ff2f3b21ae2c43c77c2833
      I have a lot of math in it. Leave me there a comment too.

Drop a comment

Your email address will not be published. Required fields are marked *