0
$\begingroup$

I need to learn approach to solve following problem, I need this for programming problem.

For a given set of alphabet letters $S$, and pairs of rule and find the number of ways in which $N$ length different strings can be formed.

$\underline{Examples}:$

Given a set of letters $S=\{a, b, c\}$, we have replacement rules $(current\_letter, next\_ letter)$ as below:

$$ \{ (a, a), (a, b), (a, c), (b, a), (b, c), (c, a), (c, b) \} $$

How to calculate the number of ways that $N$ length string can be formed such that two consecutive pairs always appears in replacement rules.

For $N = 1$, we have 3 ways either { "$a$", "$b$", "$c$" }
For $N=2$, we have 7 ways { "$aa$" "$ab$", "$ac$", "$ba$", "$bc$", "$ca$", "$cb$" }
For $N=3$, we have 17 ways { "$aaa$", "$aab$", "$aac$", "$aba$", "$abc$", "$aca$", "$acb$", "$baa$", "$bab$", "$bac$", "$bca$", "$bcb$", "$caa$", "$cab$", "$cac$", "$cba$", "$cbc$" }

Please give me hint, what should I read to sovle this?

$\endgroup$
1
  • 2
    $\begingroup$ The rules prohibit having consecutive $b$s or consecutive $c$s. Have you tried to construct a recurrence relation? $\endgroup$ – N. F. Taussig Jun 4 '19 at 9:06
2
$\begingroup$

Not a complete answer, but especially because you need it for programming I think it might be useful.

For $n=1,2,\dots$ let $A_n,B_n,C_n$ denote the number of stringths having length $n$ that end on $a,b,c$ respectively, and let $T_n$ denote the number of stringth having length $n$.

Then $A_1=B_1=C_1=1$ and:

  • $T_n=A_n+B_n+C_n$
  • $A_{n+1}=T_n$
  • $B_{n+1}=A_n+C_n$
  • $C_{n+1}=A_n+B_n$
$\endgroup$
3
  • $\begingroup$ Thanks, I will explore on it further $\endgroup$ – Grijesh Chauhan Jun 4 '19 at 9:18
  • $\begingroup$ You welcome. Good luck. $\endgroup$ – drhab Jun 4 '19 at 9:19
  • $\begingroup$ helped me very much. Thanks $\endgroup$ – Grijesh Chauhan Jun 6 '19 at 9:41
2
$\begingroup$

This is equivalent to counting the number of paths of length $N-1$ in a directed graph whose vertices are letters, and where there is an edge from $v$ to $w$ if and only if $(v,w)$ is a rule. Letting $A$ be the adjacency matrix of this graph, where $A_{i,j}=1$ if there is an edge from $i$ to $j$ and $A_{i,j}=0$ if not, it is well known that the $(i,j)$ entry of $A^k$ gives the number of directed paths of length exactly $k$ from $i$ to $j$. Therefore, to compute the number of all paths, you just need to add up all the entries in the matrix exponent $A^{N-1}$. This can be computed in $|S|^3\log N$ time using exponentiation by squaring.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer, I draw the execution tree by hand (like I drawn in linked answer) It was tree for me instead ... indeed I am looking for an efficient solution --- my current implement ion not good when $N > 1000000$ $\endgroup$ – Grijesh Chauhan Jun 6 '19 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.