I was doing a coding test (already finished, so no cheating for me) and came across this problem, which I'll describe in few steps:

  1. We have a keypad, like on cellphones, with keys from 1 to 9, where 1 is the space key (" ") enter image description here
  2. We are given a message to convert to numbers based on the "distance" of each letter (P = 7, S = 7777, K = 55, ...), for example DRSA becomes 377777772
  3. Now we need to calculate the the number of the possible messages we could write with that same number (DPPPPPPPA, DPPPPPQA, ...)

The method I came up with is the following:

  1. I split the number by its different digits obtaining for example 3, 7777777, 2
  2. I ignored single digits as they do not add "value" to the permutations (as far as I understood it)
  3. I take each section of digits and based on its length (in this case 7 digits) I calculate every possible permutation and count them

Now this method works, but it's slow so I wanted to find a way to calculate the number of these permutations without counting them manually.

I found out about integer compositions, which in my case should have a maximum value. In this case the key 7 has a maximum value of 4 so its composition would be something like this:

  • 4+3
  • 3+4
  • 4+1+2
  • 4+2+1
  • 1+2+4
  • 1+4+2
  • ...

How can I limit the maximum value of the composition (4) of a number (7)? How can I know the number of elements in it?


For numbers limited to $3$ you have the Tribonacci numbers, OEIS A000073, which begin $$ 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504,$$ and for numbers limited to $4$ you have the Tetranacci numbers, OEIS A00078 which begin $$ 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490,$$ Each number in the Tribonacci series is the sum of the previous three, because to get a composition of $n$ you can take a composition of $n-1$ and add a $1$, a composition of $n-2$ and add a $2$, or a composition of $n-3$ and add a $3$.

  • $\begingroup$ Didn't know this one! Could you explain to me the last part, because I didn't understand it, what do you mean by "to get a composition of n you can take a composition of n−1 and add a 1, ..."? $\endgroup$ – Xriuk Dec 30 '18 at 18:54
  • $\begingroup$ And if I had a key with 5 characters? I would use something like a "pentanacci"? OEIS A052918 $\endgroup$ – Xriuk Dec 30 '18 at 19:04
  • $\begingroup$ The last justifies the recurrence. If I have a composition of $13$ and are limited to $3$, consider the last digit. If it is $1$, you have a composition of $12$ left when you erase the $1$, so the number of ways to get $13$ is the sum of the ways to get $10, 11,$ and $12$ because you can append the appropriate digit at the end. Yes, if you had a key with $5$ characters you would have each number the sum of the preceding $5$ for the same reason. $\endgroup$ – Ross Millikan Dec 30 '18 at 19:07

How can I know the number of elements in it?

Two-variable recurrence. If $a_m(n, k)$ is the number of compositions of $k$ numbers from $1$ to $m$ which total $n$ then $$a_m(n, k) = \begin{cases} 0 & \textrm{if } n < 0 \\ 1 & \textrm{if } n=0, k=0 \\ 0 & \textrm{if } n=0, k \neq 0 \\ \sum_{i=1}^m a_m(n-i, k-1) & \textrm{otherwise} \end{cases}$$

For practical computation, you would want to use dynamic programming.


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.