Permutations excluding repeated characters

Question

I'm working on a Free Code Camp problem - http://www.freecodecamp.com/challenges/bonfire-no-repeats-please

The problem description is as follows -

Return the number of total permutations of the provided string that don't have repeated consecutive letters. For example, 'aab' should return 2 because it has 6 total permutations, but only 2 of them don't have the same letter (in this case 'a') repeating.

I know I can solve this by writing a program that creates every permutation and then filters out the ones with repeated characters.

But I have this gnawing feeling that I can solve this mathematically.

First question then - Can I?

Second question - If yes, what formula could I use?

To elaborate further -

The example given in the problem is "aab" which the site says has six possible permutations, with only two meeting the non-repeated character criteria:

aab aba baa aab aba baa

The problem sees each character as unique so maybe "aab" could better be described as "a1a2b"

The tests for this problem are as follows (returning the number of permutations that meet the criteria)-

"aab" should return 2
"aaa" should return 0
"abcdefa" should return 3600
"abfdefa" should return 2640
"zzzzzzzz" should return 0

I have read through a lot of post about Combinatorics and Permutations and just seem to be digging a deeper hole for myself. But I really want to try to resolve this problem efficiently rather than brute force through an array of all possible permutations.

I posted this question on math.stackexchange - https://math.stackexchange.com/q/1410184/264492

The maths to resolve the case where only one character is repeated is pretty trivial - Factorial of total number of characters minus number of spaces available multiplied by repeated characters.

• "aab" = 3! - 2! * 2! = 2
• "abcdefa" = 7! - 6! * 2! = 3600

But trying to figure out the formula for the instances where more than one character is repeated has eluded me. e.g. "abfdefa"

Answer 1

This is a mathematical approach, that doesn't need to check all the possible strings.

Let's start with this string:

abfdefa

To find the solution we have to calculate the total number of permutations (without restrictions), and then subtract the invalid ones.

---

TOTAL OF PERMUTATIONS

We have to fill a number of positions, that is equal to the length of the original string. Let's consider each position a small box. So, if we have

abfdefa

which has 7 characters, there are seven boxes to fill. We can fill the first with any of the 7 characters, the second with any of the remaining 6, and so on. So the total number of permutations, without restrictions, is:

7 * 6 * 5 * 4 * 3 * 2 * 1 = 7! (= 5,040)

---

INVALID PERMUTATIONS

Any permutation with two equal characters side by side is not valid. Let's see how many of those we have. To calculate them, we'll consider that any character that has the same character side by side, will be in the same box. As they have to be together, why don't consider them something like a "compound" character? Our example string has two repeated characters: the 'a' appears twice, and the 'f' also appears twice.

Number of permutations with 'aa' Now we have only six boxes, as one of them will be filled with 'aa':

6 * 5 * 4 * 3 * 2 * 1 = 6!

We also have to consider that the two 'a' can be themselves permuted in 2! (as we have two 'a') ways. So, the total number of permutations with two 'a' together is:

6! * 2! (= 1,440)

Number of permutations with 'ff' Of course, as we also have two 'f', the number of permutations with 'ff' will be the same as the ones with 'aa':

6! * 2! (= 1,440)

---

OVERLAPS

If we had only one character repeated, the problem is finished, and the final result would be TOTAL - INVALID permutations.

But, if we have more than one repeated character, we have counted some of the invalid strings twice or more times. We have to notice that some of the permutations with two 'a' together, will also have two 'f' together, and vice versa, so we need to add those back. How do we count them? As we have two repeated characters, we will consider two "compound" boxes: one for occurrences of 'aa' and other for 'ff' (both at the same time). So now we have to fill 5 boxes: one with 'aa', other with 'ff', and 3 with the remaining 'b', 'd' and 'e'. Also, each of those 'aa' and 'bb' can be permuted in 2! ways. So the total number of overlaps is:

5! * 2! * 2! (= 480)

---

FINAL SOLUTION

The final solution to this problem will be:

TOTAL - INVALID + OVERLAPS

And that's:

7! - (2 * 6! * 2!) + (5! * 2! * 2!) = 5,040 - 2 * 1,440 + 480 = 2,640