I am not a math expert, but I have been reading about permutations and I am trying to write an algorithm to solve a freecodecamp challenge. My algorithm has passed all the tests except for one test
Given a string of letters of 'aaabb', how many ways can we arrange the letters so that there are no repeated letters adjacent to another. Visually, I can see that A-B-A-B-A is the only way we can arrange the letters. And I can see 3As = !3 and 2Bs = !2 therefore the answer is 12 different ways. However, I am trying to solve all the challenges and my algorithm just can't seem to solve this one.
Let me explain how I am calculating the # of permutation and perhaps you can point me where I am doing something incorrectly.
1) I start of my determining the total possible permutation, so 5 letters = !5
2) I count the # of repeated letters: here I have !3 for A, and !2 for B.
3) I subtract from the total possible permutations the total # of invalids combinations. This turns out to be 3 calculations.
Calculation 1: I know 'AAA' can only fit into 5 slots 3 ways. 'AAA' fits as AAABB, as BAAAB, and as BBAAA, so 'AAA' is !3 * 3 slots * 'BB' is !2. # of invalids for using a sequence of 'AAA' is 36 or !3!2 * 3.
Calculation 2: I know that 'BB' can fit into 5 slots 4 ways. 'BB' fits in as BBAAA, as ABBAA, as AABBA, and as AAABB, so 'BB is !2 * 4 slots * !3 for 'AAA' is 48
Calculation 3: we haven't considered 'AA' yet, so we do now and this calculation can be treated the same as Calculation 2. !2 for 'AA' * 4 slots !3 for 'ABB' = 48.
Total Invalids = 132.
I know what you are thinking: 120 permutation - 132 invalids = -12 ??? I haven't removed the OVERLAP calculation of invalids which occurred by performing calculations 1 & 3.
My problem, I'm sure, is with my calculation of the OVERLAPS.
Edit:
Sorry if my question was not clear as I was trying to be very clear by giving the correct answer to the # of permutations to this problem. As it turned out I was stuck on this problem for over 3 days, but I fixed my algorithm by correcting my computation of the OVERLAP equation.
For those that found their way here via freecodecamp.org you can find my algorithm at https://jsperf.com/permalone-eggs
You are completely right: there are many overlaps in your calculations. Say, variants BBAAA appear in Calculation 1 and in Calculation 2.
There are $\binom{5}{2}=10$ ways to put two letters B in 5 places. Nine of them are invalid:
BBAAA, BABAA, BAABA, BAAAB, ABBAA, ABAAB, AABBA, AABAB, AAABB.
So, there are $9\cdot 3!\cdot 2!=108$ invalid combinations, if all letters are distinct.