The "No Repeats Please" Challenge

I think I’ve figured out the basic math for pairs - but only if those pairs are of a different type. This works for the “abfdefa” example, but would not work, say, if the string was “abadeaa”. I’m still trying to work out how it work for n+ repeats. Hopefully seeing how it works for “abfdefa” will point in the right direction of writing algorithms for pairs of the same type, and triplets of a different type. Then it’s clever coding to figure out how to reduce the lines of code.

[FIRST PAIR]
Ok, so, first, I slice the input string into an array of singles and mutiples. So “abfdefa” > [“bde”,“aa”,ff"].

Let’s just assume for the moment that “ff” is “fe”. To find the amount of non-repeating permutations, there will be the total amount of permutations (with repeats) - the number of permutations that have repeats. The total amount of permutations will equal the factorial of the input string length. If length(“abfdefa”) is equal to 7, then 7!.

So far, we know then that the number of perms (without reps) will equal 7! - x, where x is the number of permutations containing combination “aa”. How do we find x?

We can find x, by considering the number of position we can insert “aa” into “bdeff”. We do this by drawing up “bdeff” as follows. _ B_D_E_F_F_ . We see that “aa” can be insert into any space between the letters, or either of the spaces on the outside. The number of possible positions is determined by length(“bdeff”) + 1. This gives us 6 possible places “aa” can be placed. Since “aa” can be switched around, there will be more than one permutation for each of the possible placements. Because length(“aa”) is 2, then we know that the amount of permutation is equal to 6 * 2! = 12. But for each of these 12 permutations, we can also switch “BDEFF” around 5! times. So the amount of permutations containing pairs, will equal: 5!* 6* 2! . This formula returns the value 1440.

So, the number of permutations that do no contain pair “aa” will equal
7! - (5!* 6* 2!) = 5040 - 1440 = 3600. This is enough math to solve the “abcdefa” example.

[SECOND PAIR]
For the second pair, which is “ff”, we can simply apply the same algorithm above to determine the amount of permutations which contain pairs of “f”. This will also be 1440. That simple? No! We have to consider that some of the pair-permutations of “aa” will contain some permutations which “ff” and vice versa. If we do a venn, we get a visual picture of the intersection:
{ “aa”:1440 [ “aa”&“ff”: ??? } “ff”:1440 ].

How do we get the number for “aa” & “ff”? Well, since we know that either “aa” or “ff” yields 1440 permutations, we can do further search within either. To get the number of pairs of “ff” within the set of all permutations containing “aa”, we repeat some of the logic from above, but set the problem up differently.

This time, rather than treating “aa” as seperate characters, where going to treat it as a block. So the position set up will look like this. _ AA_B_D_E_ . This gives us 5 possible position where “ff” could be placed, so 52! gives 10 permutations for one permutation of “aabde”. Now, to get the total number of permutations, rather than assuming that all characters can be switched around, we know that only “bde” can be switched around because “aa” must be kept together. So rather than multiplying (52!) by 5!, we will only multiply it by 4!. As well as this, because we have ANOTHER pair “aa” we need to multiply 4! by 2!. This yields a total function of 4!2! * (5*2!) which equals 480.

So then, to get the number of pairs (n =1) of two types, we use the following calculation.

7! - ((5!* 6* 2!) - [(5!* 6* 2!) - (4!2! * (5*2!)]
= 5040 - 1440 - (1440 - 480)
=5040 - 1440 -960
=2640

If I get a more concise algorithm, I’ll post it. I suspect number of repetitions will mean something like:
1 pair: (5!* (62!)
2 pair: (4!2!
(52!)
3 pair: (3!2!2!
(4*2!)… and so on

Here is my solution.

The code isn’t pretty, and it is a little complex, but it run a lot faster on big string that the brute force solution.

By example it run almost instantly on permAlone(‘aaaeeefghijkl’);
(it is equal to 2146798080)

Thanks to your benchmark program i could test my solution :slight_smile:

Here is the result i get (my program is the last one) :
732.5749999999998 5847.09 3286.6900000000005 23.46000000000094

https://www.repl.it/Cx3H/2

On a more complex test (permAlone(“aaabbccdefgh”)) (i removed the slower programs to avoid to freeze my browser) :
125721.66 374.70500000000175

We see that the time gaps is growing quickly.

hey jjames, thanks for the solution. I was wondering if you can walk me through the code? And some tips as to how to go about solving such problems, I always end up getting stuck at such problems.

here, i wrote this out for someone a few months ago, it should be helpful

1 Like

Wow Thanks! One more help… how does one go about building intuition for recursive solutions such as these , since they don’t come to me naturally compared to other sort of algorithms ? Any tips will be very helpful.

I use the same kind of reasoning that what i do in math when i use recursive reasoning :

  1. I consider i had already the function i want, to solve the problem for “n”.
  2. I build a function to solve the problem for “n+1”, using the previous function.
  3. I found what will be the “n=0”, and what i will return for that, so my function can end.

Now what is “n”, “n+1”, and “n=0”, will depend of the problem i try to solve.

I have an advanced solution here on my GitHub Gist. I generate no permutations, just factorials and mathematical calculations for any input given (the implementation is limited to 32 bits but I gave a suggestion for larger strings in my explanation)

1 Like

the @mesterum solution is really impressive - it ran 4 orders of magnitude faster than the @dionisos2 solution for "aaaeeefghijkl" in the performance tests posted above - the @jjames solution is straightforward and compact but it was taking too long for this test case and I had to kill it

1 Like

Hey :slight_smile: , It is good to see some other people interested in this challenge.

@mesterum solution is pretty good, but still slower than my best solution, which is itself slower than “David_f25” solution.

Here are my benchmark :
benchmark permAloneSuperPatternOpti very complex : 150.52
benchmark permAloneDavidF25 very complex : 31.45
benchmark permAloneMesterum very complex : 1060

Very complex is for permAlone(“aaaaaaaaabbbbbbbbbbccccccccddddeeeeeefffgggghhhhij”), it is equal to approximately 5.15302338787e+61

permAloneSuperPatternOpti is the best solution I was able to found.
I explain this solution [here]

I should have sharing it before, but I felt a little shame about my bloated source code now that I understand programming a little better, I also wanted to improve my explanation and understand David_f25 solution (yes, because I still don’t understand it).
The thing is, I will probably never do it, because I have less time now.

Where is your benchmark?
I took your code from https://codefights.com/challenge
change a bit in magicRecipeOfProtection and getReps functions to work but I found not to match your benchmark results.
DavidF25 code was in C++
Has codefights.com/ an option for benchmarks? I’m new on codefights.com/.

I concur with @mesterum - the @dionisos2 permAloneSuperPatternOpti solution is much faster than the earlier @dionisos2 solution but still 2-3X slower than the @mesterum solution

I tested "aaabbccdefgh" and "aaaeeefghijkl"

I also tested the DavidF25 js code at https://github.com/dionisos2/no_repeat_please/blob/master/david-f25.js

it is about 40% slower than @mesterum solution

@mesterum Sorry, I forgot to share the link to the benchmark, it is here.
You should open “no_repeats_plz.html” to see the result.
All my code is unnecessarily ugly, so if you have hard time understanding it, don’t try too hard, tell me, and I will fix it.

You can see I translated the David_f25 solution in javascript to do the test, here

@ppc, @mesterum, there is a difference in time complexity, like you said, for medium input as “aaabbccdefgh”, the mesterum solution can be faster, but when you try big input, like “aaaaaaaaabbbbbbbbbbccccccccddddeeeeeefffgggghhhhij”, mesterum solution start to be a lot slower.

Anyway the mesterum solution is very ingenious and I am unsure I would have been able to discovers it if I had go on the same path than him.
This problem seems to be very open and allow all kind of interesting solutions.

Has codefights.com/ an option for benchmarks? I’m new on codefights.com/.

No, aside from the fact that too slow solutions will be rejected.

Ok I put some order in my code.
All the tests and benchmarks are in main.js.

Here is the output I get :

Test simple for permAloneBruteForce : true
Test simple for permAloneBruteForceOpti : true
Test simple for permAlonePattern : true
Test simple for permAloneAlbinutte : true
Test simple for permAloneProgheal : true
Test simple for permAloneSuperPatternOpti : true
Test simple for permAloneMesterum : true
Test simple for permAloneDavidF25 : true
Test complex for permAloneSuperPatternOpti : true
Test complex for permAloneMesterum : true
Test complex for permAloneDavidF25 : true

------------- "aaaeei" -------------

Benchmark for permAloneBruteForce : 5.52
Benchmark for permAloneBruteForceOpti : 1.84
Benchmark for permAlonePattern : 1.40
Benchmark for permAloneAlbinutte : 0.56
Benchmark for permAloneProgheal : 2.60

------------- "aaabbccdefgh" -------------

Benchmark for permAloneSuperPatternOpti : 0.31
Benchmark for permAloneMesterum : 1.60
Benchmark for permAloneDavidF25 : 1.54

------------- "aaaaaaaaabbbbbbbbbbccccccccddddeeeeeefffgggghhhhij" -------------

Benchmark for permAloneSuperPatternOpti : 111.88
Benchmark for permAloneMesterum : 1040.55
Benchmark for permAloneDavidF25 : 31.43

It seems that for “aaabbccdefgh” I don’t get the same result than @ppc.
It is also strange that Mesterum and David_F25 solutions are so near of each other for medium inputs. (I maybe have a mistake in my benchmark, but I don’t see where).

Oh… this one really hurt my ego. I was stuck on passing the last test for a few days.

In the end I have 2 versions of my code: Eggs, and Eggs - Table, posted in jsperf and they seem to benchmark pretty good to the Advanced. Feel free to test against my code for comparison.

:Edit: I solved it. My problems were that the functions I made weren’t in the permAlone() (not exactly sure why this matters but I’m a newb), and there was something fishy about calling perm() with the results from swap() stored into the ‘array’ outside of the even/odd if statements (so I called swap() inside of perm() inside the even/odd if statements).

Updated spoiler code:

function permAlone(str) {
  var permutations = [];
  var regExp =  /(.)\1+/gi;
  
	// Creates a permutation list
  function perm(length, array) {
    if (length > 1) {
      for (var i = 0; i < length - 1; i++) {
        if (!length % 2) {
	        perm(length - 1, swap(array, 0, length - 1));
        } else {
	        perm(length - 1, swap(array, i, length - 1));
        }
      }
      perm(length - 1, array);
    } else if (!array.match(regExp)) {
    	permutations.push(array);
  	}
  }

  //	Use to swap characters
  function swap(arr, a, b) {
    var temp = arr;
    arr = arr.split('');
    arr.splice(a, 1, temp.charAt(b));
    arr.splice(b, 1, temp.charAt(a));
    return arr.join('');
  }
  
  perm(str.length, str);

  return permutations.length;
}

permAlone("123");

My brain hurts. I followed the Heaps formula, then made a swap function, then filtered out 2+ chars next to each other, then returned the length of permutations without repeating chars. When testing “aab” it returns 2 but I still get an X by the “returns 2” for testing "aab"
Side note: it returns a different number than desired when testing others.
Thanks in advance for any help!

Here is my code thus far:

var permutations = [];

function perm(length, array) {
  if (length == 1) {
    permutations.push(array);
  } else {
    for (var i = 0; i < length - 1; i++) {
      if (length % 2 == 0) {
        array = swap(array, i, length - 1);
      } else {
        array = swap(array, 0, length - 1);
      }
      perm(length - 1, array);
    }
    perm(length - 1, array);
  }
}

//	Use to swap characters
function swap(arr, a, b) {
  var temp = arr;
  arr = arr.split('');
  arr.splice(a, 1, temp.charAt(b));
  arr.splice(b, 1, temp.charAt(a));
  return arr.join('');
}

function permAlone(str) {
  perm(str.length, str);

  var regExp =  /(.)\1+/g;
  var result = permutations.filter(a => !a.match(regExp));
	console.log(result.length);
 	return result.length;
}

permAlone("aab");

```[spoiler]This text will be blurred[/spoiler]