2
$\begingroup$

Problem: Given an arbitrary, finite alphabet $\Sigma$ with $|\Sigma| > 1$, define the language

$\qquad L = \{w \in \Sigma^* \mid w \text{ has no subword of the form } aaa, a \in \Sigma\}$.

Let $L_n = L \cap \Sigma^n$. Determine $|L_n|$; either a closed form or efficient computation scheme is desired.

Example:

Let $\Sigma = \{a, b\}$. Then, $aabaa, ababa, baaba \in L_5$ but $aaabb, baaab,aabbb \notin L_5$.

Note:

This isn't homework or anything... I am a developer at Oklahoma University and this question came up in a discussion with some fellow developer friends of mine. I have some C# code that uses recursion but I believe it to be far from efficient. I can post it if anybody is interested in looking at it as well.

  • 0
    Can (e.g.) 'A' appear in C twice? If so, how does that affect constraints 2 and 3?2011-12-08
  • 0
    Are 'string' and 'string permutation' the same here?2011-12-08
  • 0
    @msh210: "Twice in a row" is idiomatic. It means "two times in succession". There's no actual row.2011-12-08
  • 0
    Define 'row", and no characters in C[] are unique... editing post to reflect that.2011-12-08
  • 0
    Original posted edited for clarification.2011-12-08
  • 0
    @Brandon:I guess you are using some sort of backtracking or dynamic programming to brute-force the results?2011-12-08
  • 0
    @MaX I am not sure what you mean. I just wrote a simple recursive method in C# that I am sure is less than efficient.2011-12-08
  • 0
    You could use dynamic programming with memorization that would increase your efficiency :)2011-12-08
  • 0
    @MaX I say it is less than efficient because I calculate ALL possible permutations without constraint using the characters in C[] and than using String methods filter out the ones I do not want.2011-12-08
  • 0
    @MaX Not sure what you mean by "memorization" and "dynamic programming". New concepts on me! It is amazing how I still learn new stuff every day even after being a programmer for 10 years.2011-12-08
  • 0
    @Brandon:It's elementary algorithm analysis :) [Here](http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static) is a nice application based tutorial. In short if you have the recurrence relation you can always use dynamic programming to make it fast! :)2011-12-08
  • 0
    @Brandon:Sorry for my initial spelling mistake I meant [Memoization](http://en.wikipedia.org/wiki/Memoization)2011-12-08
  • 0
    So, to put it in terms perhaps more familiar to math people, you have a set $C$ of $n$ letters and want to know how many words of length $L\ge n$ there are with no $3$ successive letters identical.2011-12-08
  • 0
    ...oh. And what those words are.2011-12-08

3 Answers 3