No repeats please, from brute force to super pattern!

Project Feedback
#1

Hi everyone !

I am very happy to announce i just finished my little project (warning : it takes time to run), which was to find the quickest solution to the “no repeats please” challenge (the most interesting javascript algorithmic challenge by far).

I wrote five different solutions to this challenge (the first two aren’t from myself, but i added them to compare speed):
[temporarily deleted]

Just to give an example, “permAloneSuperPatternOpti(‘aaaaabbbbbbccccddeeeefghij’)” is calculated in only 30 milliseconds on my computer, and it is equal to 15232742249177350000000000

If everyone is interested in it, and want more explanation, please tell me :slight_smile: (i will maybe write a article about it, but i first want to see if anyone is interested)

1 Like
#2

This is very interesting (and awesome) and I’m glad that you posted it!

I was stuck on this problem for… much longer than I would like to remind myself because I tried to find a mathematical solution that doesn’t involve generating and storing the permutations at all—I got as far as having a general solution for a string with letters repeated only once but couldn’t generalise it to letters repeated more than once.

I also tried to solve the problem with patterns like you did but gave in to the pressure of moving along and gave in to Google + Wiki (which lead to Heap’s algorithm). .___.

Would definitely love to read about it if you ever end up writing about it. :slight_smile:

1 Like
#3

Thank you !, it is really motivating to see someone is interested by it :slight_smile:

I was stuck on this problem for… much longer than I would like to remind myself because I tried to find a mathematical solution

Me too, i gone through at least 6 wrong paths in total, almost abandoned and did the permAlonePattern solution. Then i had a new idea, which lead to the permAloneSuperPattern solution.
The permAloneSuperPatternOpti solution is almost a mathematical solution, we can easily locally optimize it, but i don’t think we can really found a better general solution than that (but i would be happy to be proven wrong).

I got as far as having a general solution for a string with letters repeated only once but couldn’t generalise it to letters repeated more than once.

I am interested to see what you did here.

Would definitely love to read about it if you ever end up writing about it. :slight_smile:

Yes, i think i should write something because it is almost impossible to understand my code if you don’t know how i solved the problem.
I will contact you back when the article is written :slight_smile:

1 Like
#4

I see!

I was silly and was working through my solutions just on the FCC editor and didn’t save the code that didn’t work in the end. At the time I was quite frustrated and couldn’t be happier to get rid of the terrible partial solution but realised later that I could have revisited it a lot easier had I saved it.

In any case, the mathematical solution that I was working on involves working out solutions are not allowed by grouping letters together (that is, solutions with two of the same letters next to each other), and then subtract them from all possible permutations.

If we use "abcdefa" for example, the number of permutations that are not allowed is anything that have "aa" in it—if you treat aa as one letter, then the number of disallowed permutations calculated this way is simply 6! = 720. Since the two "a"'s are treated as different, the total number of disallowed permutations is therefore 6! x 2 = 1440, which produces the correct answer of 3600 allowed permutations for the string "abcdefa".

If we then take "abfdefa" as an example, where "a" and "f" are doubled up, the solutions is actually simply 7! − (6! x 2 - 5! x 2) x 2 = 2640. The additional 5! x 2 in the parentheses in this case is because, in the 6! x 2 number of disallowed solutions where "aa" exists, there are 5! x 2 number of those solutions where "ff" also exists. The x 2 outside of the parentheses is simply because the number of solutions where only "f" is doubled up is the same as where only "a" is doubled up.

A general solution is available for strings with any number of doubled up characters this way! I was unable to generalise it further to strings with letters that are repeated more than once though. :frowning: That was the point where I attempted to use patterns—and eventually gave up because I spent way too much time on it. Scratch head

1 Like
#5

Hey, it is really pleasant to hear, that somebody has the same problem as you, had taken the same approach & came to the same result as you have… :slight_smile:
I was struggling with this same assignment for a very long time, too & I have not solved it completely. (Although, my solution passed the tests provided, I could not come up with a solution for the case when a letter is repeated more than twice. I know my solution should be improved, but I could not figure out, how to generalize it.)
Yes, I found some working solutions out on the web, but I wanted to figure out the solution independently. Moreover, those solutions were not based on mathematics & I wanted to find out the result through a mathematical calculation, as you did.
The things got complicated for me when I had to implement the inclusion-exclusion principle… I could not grasp it entirely & had neither enough time nor satisfying previous mathematical knowledge to dive into the problem on my own.

#6

Lol, just finished a post here about noone analyzin the problem deeply before getting to start coding, then ends with a neverending function, if he puts in like 20+ character string. Then I found your thread ironically. But np., man Im still happy atleast smone gets to thinking before coding, which in my opinion, is the most precious ability of a coder. GJ

#7

Did u tried to sign same characters with numbers?

When I stucked on bad result on more same characters then 2, i knew i need to find those multiple times substracted permutations. To find them, u need to identify them first. So for example "aaabc"
u go like

5! - 3!*4!

then u need to add back those repetitive substracted, but what are they? To find out I did:

“(a1a2)a3bc” is same order (permutation) as “a1(a2a3)bc”

So what Im looking for?
Im lookin for all permutations of that specific order of a’s (in this example a1a2a3)
so its like

“(a1a2a3)bc” and therefore theres 3! permutations

I need to cover all posible orders of a’s (a1a2a3, a1a3a2 … ) which again is 3! (sum of all permutations of three a’s) so I need to add back 3!*3!

so the right formula is

No Repeats Please ( “aaabc” ) = 5! - 3! * 4! + 3! * 3!

Problem solved. Same logic to all possible combinations and u can get through.

Then there is another chalenge and this is to assign the right variables to be able to code it with one universal formula (that was quite chalenging)

I hope this’ll help ya get back to this issue, bcs u were on a right path.

1 Like
#8

Thank you very much for the suggestion! I found that in this case it’s not actually necessary to number them because one of the conditions of the problem is that the same letters are still treated as unique when calculating permutations.

In the end I brute forced it with Heap’s algorithm in favour of spending days trying to find a solution numerically (because at that point I have already spent a couple of days on it).

#9

Hi ondraash, is it great to see someone else interested by this kind of challenge.

Do your solution generalize at more groups of more similar letters ?
permAlone(“aaaaaaaabbbbcccddeeefgh”) give me 263645724300882740000, do you find the same thing ?

Here I wrote a explanation of my solution :-).