• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

ABC's isn't always the correct order

 
William Koch
Ranch Hand
Posts: 76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20555
57
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How about XABCXABCX? That's two occurrences of ABC instead of one.
 
William Koch
Ranch Hand
Posts: 76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 2987
12
Firefox Browser IntelliJ IDE Java Mac Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 21152
32
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 2987
12
Firefox Browser IntelliJ IDE Java Mac Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yep, I just coded that up and it worked.

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

 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic