1
$\begingroup$

Given a list $C=[c_1,c_2,\dots,c_k]$ of positive integers, representing the values of $k$ varieties of coins, and a positive integer $n$, let $f(n,C)$ be the number of handfuls of coins with total value $n$. The order within the handful does not matter, and there is an infinite supply of each variety of coin.

What is the state-of-the-art algorithm to compute $f(n,C)$?

Equivalently, $f(n,C)$ is the number of ways to choose non-negative integers $x_i$ so that $n=\sum_{i=1}^k x_ic_i$.

The list $C$ can have repeats, and the interpretation is that there are two varieties of coin with the same value. For example, $f(3,[2,1,1])=6$. Letting $A$ and $B$ be the coins of value $1$, and $C$ be the coin of value $2$, the $6$ possible handfuls are $$ (A,A,A),(A,A,B),(A,B,B),(B,B,B),(A,C),(B,C) $$

I can think of two solutions. Which is faster depends on $n$ and $C$.

  • Dynamic programming: Let $C'$ denote $C$ with its last entry removed. A use-it-or-lose-it argument gives $$f(n,C) = f(n-c_k,C)+f(n,C') .$$ This lets you compute $f(n,C)$ by filling out an $n\times k$ DP table, which takes $$\boxed{\Theta(nk)}$$ additions and look-ups.

  • Matrix exponentiation: I will illustrated in the case $C=[2,3,4]$. Letting $a_n=f(n,C)$, then $a_n$ satisfies the recurrence (see https://cs.stackexchange.com/a/87810/24590) $$ a_n = a_{n-2}+a_{n-3}+a_{n-4}-a_{n-5}-a_{n-6}-a_{n-7}+a_{n-9} $$ Any linear recurrence can be solved by computing the $n^{th}$ power of a certain matrix. In this case, the recurrence has order $c_1+\dots+c_k$, so this algorithm takes $$ \boxed{O(\log n \cdot M(c_1+\dots+c_k))} $$ arithmetic operations, where $M(k)$ is the number of arithmetic operations required when multiplying two $k\times k$ matrices (naively $M(k)=k^3$, state of the art is $k^{2.3728639}$). We get $\log n$ by using exponentiation by squaring.

The second algorithm is asymptotically much better as $n\to\infty$, but the first is better when the sum of $C$ is large.

Are there any known faster algorithms?

$\endgroup$
2
$\begingroup$

From a theoretical perspective, you can diagonalise (well, decompose to Jordan normal form) to do the matrix power. It costs $O(M(c_1+\dots+c_k))$ to decompose, $O(\log n \cdot (c_1+\dots+c_k))$ to raise the diagonal matrix to the $n$th power, and $O(M(c_1+\dots+c_k))$ to finish up.

$\endgroup$
  • $\begingroup$ Good observation. The eigenvalues of this particular matrix are $c_i^{th}$ roots of unity, so I suppose in order to avoid floating point math and rounding errors you would have to work in $\mathbb{Q}[\zeta]$ where $\zeta$ is an lcm$(c_1,\dots,c_k)$ root of unity. $\endgroup$ – Mike Earnest Jan 29 at 16:58

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.