This week's book giveaway is in the Design forum.We're giving away four copies of Design for the Mind and have Victor S. Yocco on-line!See this thread for details.
Win a copy of Design for the Mind this week in the Design forum!

# ABC's isn't always the correct order

William Koch
Ranch Hand
Posts: 76
Using only letters A B & C, how many different messages of length N can you type? with the constraint that ABC cannot appear anywhere in the string. For example, typing BACBBC would be fine, but typing BCABCB would not. With this constraint, how many different messages of length N can you type? Does anyone know how to solve it using recursion?

N is the length so my solution so far say if it starts with an B or C then there are f(N-1) ways the rest of the string could be arranged. If it starts with an A then there are 4*f(N-3) ways we can arrange it. Therefore:

f(N) = f(N-1) + f(N-1) + 4*f(N-3).... this is incomplete can anyone point me in the right direction?

Jayesh A Lalwani
Rancher
Posts: 2756
32
You don't really need recursion

total number of possible messages of Length N using 3 letters = 3^N

total number of messages that have ABC are
ABCXXX....
XABCXX....
XXABCX....
.
.
.
....XXXABC

This is always going to be N-2

So, total number of legal messages = 3^N - N + 2

William Koch
Ranch Hand
Posts: 76
Jayesh that will not work. For example if there is a string of length 5 then there are 3^5 ways to arrange those 3 characters (you can resuse them) so 3^5=243 , now we need to look through those 243 and find out which ones have the string ABC in it, count those and subtract that count from 243 to get our answer in this case the correct answer would be 216 ( there are 27 strings where ABC appears). Your approach does not hold for all cases.

Rob Spoor
Sheriff
Posts: 20511
54

William Koch
Ranch Hand
Posts: 76
my point exactly. There is a way to do this where you can use recursion and I started it at the beginning of the thread but it is incomplete does anyone know how to complete this and take into account duplicates, triplets, etc? If my initial part is incorrect please let me know.

Greg Charles
Sheriff
Posts: 2985
12
Jayesh had the right idea, but didn't get the combinatorics exactly right.

For something like, ABCXX...., you can't count that as 1, because there are multiple values of XX... So, instead of 3^n - (n-2), you have 3^n - (n-2)*3^(n-2). But even that isn't right, because it will twice subtract a string like ABCCCABC.

That may be where the recursion comes in. For each of n-2 positions ABC could hold, you need to multiply 3^m (where m is the number of characters left after the C) by f(k) (where k is the number of characters before the A, and f is the recursive call, ie. the number of ways those k characters could be arranged and not hold "ABC".)

Paul Clapham
Sheriff
Posts: 20952
31
You're already going in the right direction, William.

If S is a valid production of the grammar then so are BS and CS. That's the first two terms of the equation in your original post. However AS might or might not be valid... basically you now want a count of the number of valid strings of the form BCS so you can subtract that.

Greg Charles
Sheriff
Posts: 2985
12
Yep, I just coded that up and it worked.

Here's a brute force method I wrote for checking my answer: