-1

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

Jyrki Lahtonen
  • 133,153
Eggs
  • 101
  • In the challenges, are there only a's and b's or could there be more than two letters? – krirkrirk Apr 01 '18 at 20:32
  • @krirkrirk I think the OP makes it clear that we are working with three a's and two b's. – amWhy Apr 01 '18 at 20:39
  • @amWhy yes, but OP does know the answer for this case : $12$. So they're not only looking for an answer in this particular case. They want an algorithm that can solve all the challenges they're facing. This algorithm is much simplier if we're only working with two letters. – krirkrirk Apr 01 '18 at 20:43
  • 1
    There is only one way, because the a's are not distinct, nor are the b's distinct. – amWhy Apr 01 '18 at 20:46
  • @amWhy Although it's highly likely, this is not necessarily true. If a's and b's are not distinct, there is always either $1$ possibility - if #a $\neq$ #b - or $2$... which would not make this challenge very challenging. – krirkrirk Apr 01 '18 at 20:59
  • Then you should have specified that you are working with characters in ${a_1, a_2, a_3, b_1, b_2}$, in which case there are $5!$ distinct ways to arrange them, since each of the characters/letters are distinct. So since $a_1\neq a_2$, we can have a sequence with $a_1, a_2, ... $, etc. – amWhy Apr 01 '18 at 21:10
  • @amWhy I'm pretty sure the question can be rather seen as : There are 5 people in line, 3 men and 2 women ; in how many ways can they be arranged so that no gender is repeated or something like that. But I'm not OP and only them can tell. Though from a "question maker" point of vue, this is the only "challenging" way of seeing this. – krirkrirk Apr 01 '18 at 21:16
  • @krirkrirk But that's not the question that was asked. The OP asked about the number of distinct arrangements of letters three a's and 2b's, such that no a was next to a b, and vice versa. Hence to the question you asked, there is one distinct way to do so. – amWhy Apr 01 '18 at 21:29
  • @amWhy Once again, I'm not OP. Plus, I don't think there is a convention for those type of question stating "if not mentionned, letters are considered not distinct" ? – krirkrirk Apr 01 '18 at 21:37
  • @krirkrirk What if.... what if.... what if... ??? It's not our job to try to guess what the asker might mean. We have only what the asker has given us, which is a question about how many ways 3a's and 2b's can be arranged such that different letters never touched. Different letters clearly means the distinction between a and b. So $ababa$ is $ababa$ is $ababa$... only one way. I'm not going to persist in your gaming and hypotheticals any more, at krirkrirk. – amWhy Apr 01 '18 at 21:41
  • @amWhy Well OP was nice enough to give us some of their work, which clearly shows that they consider the a's to be distinct. Given that their algorithm has passed all challenges except one, we can assume that this way of seeing the question is the right one. It'd be nicer if they clearly stated that, but considering that this is a new user and that the first line is "I'm not a math expert", I feel OP made enough effort here and we should try helping them instead of "disrespecting" the question. – krirkrirk Apr 01 '18 at 21:49
  • But the OP is mistaken, which I pointed out in my first comment below the question. Especially given this is a new user, and that they really are contradicting themselves. – amWhy Apr 01 '18 at 21:51
  • @amWhy I'm not sure what makes you think OP is mistaken in their way of understanding the question. If their algorithm passed all challenges but one, it'd be very unlikely they misunderstood the question. – krirkrirk Apr 01 '18 at 21:56
  • krirkrirk You want to credit the asker with having stated clearly, given sets $A = {a_1, a_2, a_3},$ and $B = {b_1, b_2},$, how many ways are there to arrange elements from $A\cup B$, such that no element from A is next to an element of B. That's a far reach from the question the OP asked, though the OP is free to use this formulation to edit their post in an effort to reflect what they are asking, if that is what they're asking. I respect the asker enough to ask for clarification. You disrespect them by, i.e., assuming the asker meant what they didn't say. – amWhy Apr 01 '18 at 21:56
  • Let us continue this discussion in chat. – amWhy Apr 01 '18 at 22:00
  • Oh sorry, I thought I was clear with my question. allowable sequences are only those sequences where there are no adjacent repeating letters, so AABBA would be invalid, but ABABA is good. and yes think of them as A1 A2 A3, B1, B2 so that these too can be sequenced – Eggs Apr 01 '18 at 22:00
  • One other thing, this particular sequence is the final test, so it is proving to be the hardest to pass. I think it is due to the string containing AAA where as the other challenges, there was never more than 2 repeatable characters – Eggs Apr 01 '18 at 22:03
  • Please edit your post accordingly, Eggs, that's all I've asked. So if A1 is different than A2, then $A_1A_s$ can be next to one another because you specify there are no adjacent repeating letters, And $A_1 \neq A_2$, hence $A_1A_2A_3B_1B_2$ is valid. – amWhy Apr 01 '18 at 22:09
  • The term permutation refers to several ways of arranging a set of objects in a sequential order. Combination implies several ways of choosing items from a large pool of objects, such that their order is irrelevant. I was trying to calculate the permutation, but I did say that and sorry if that was not clear enough. – Eggs Apr 01 '18 at 22:33

1 Answers1

0

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.

NCh
  • 13,807
  • 4
  • 17
  • 33