Consider the following math problem.
Given an unlimited supply of coins of given denominations, find the total number of distinct ways to get a desired change...
This is a classic dynamic programming exercise, and I will explain a couple of ways to solve this problem.
First, let us translate the problem to mathematical notation:
$$f : \mathbb{N} \times [\mathbb{N}] \rightarrow \mathbb{N}$$
$$f(m,S) = \#\left\{\mathcal{S}(X) \subset S \middle| \sum X = m \right\}$$
Note that we are using braces for sets, brackets for multisets, $\mathcal{S}$ for the support function and # for cardinality.
Brute force method
The most intuitive approach is to check all possible multisets, calculate the sum, and check the sum equals the desired change. But as the number of possible multisets are infinite, this is impossible. Therefore, we will have to limit our possible multisets. One can easily see that the multiplicity of each coin has to be smaller or equal than $m/c$, with $m$ the total money and $c$ the value of the coin, limiting the total number of possible multisets to:
$$\prod_{c \in S} \frac{x}{c} = m^n\prod_{c \in S} \frac{1}{c}$$
example scala code:
def gridScan(base:Int,mx:Int): List[List[Int]] = {
if (mx==1)(0 until base).map(x => List(x)).toList
else (0 until base).map(x => gridScan(base,mx-1).map(y => x :: y))
.toList.flatten.toList
}
def change(money: Int, coins: List[Int]) : Int = {
gridScan(money/coins.min + 1,coins.length)
.map(x => (x zip coins)
.map{ Function.tupled(_ * _)}.sum)
.count(_==money)
}
The time order of this method is by consequence $O(m^n)$
Weak simplex method
Let us consider a hyperspace where each axis is the multiplicity of a specific coin. Each point in this hyperspace can be mapped to the analytic continuation of the total money that this coin makes. So, if we call $c_1,c_2, ...$ the values of the coins and $x_1,x_2, ...$ the multiplicities, then is $$\sum x_ic_i$$ the total value. Therefore, one can just check all integer multiplicities where $$\sum x_ic_i \le m$$. One could also go for equality, but solving this exact equation is harder than checking for inequality, so for this method, we use the inequality.
As this method gives no efficient way to calculate the allowed integer multiplicities, no code is provided.
The time order of this method is $O\left(\frac{m^n}{n}\right)$
Recursive method
We can build a way to construct a multiset as follows:
- select a coin with a value smaller or equal then the remaining amount of money.
- subtract the value of the coin for the pool of money.
- If you still have money, repeat.
Note that the solutions of this algorithm are not distinct, but this can easily be solved by only allowing coins that are smaller or equal then the coins selected in previous iterations.
Now, the number of ways that this algorithm can be applied is also the number of possible combinations.
This can be transformed into a recursive function.
$$f(m,S) = \sum_{y \in S} f(m-y,S| y \ge m) $$
We can forgo the check if $y \le m$ by defining $f(m,S) = 0$ for $m <0$
Note that this method checks all possibilities defined in "weak simplex method", so it has the same computational complexity, but this method describes how to actually scan them.
example scala code:
def change(money: Int, coins: List[Int]) : Int = {
if (money < 0) 0
else if (money == 0) 1
else coins.map(x => change(money-x,coins.filter(y => y>=x))).sum
}
Strong simplex method
If we call $c_1,c_2, ...$ the values of the coins and $x_1,x_2, ...$ the multiplicities, then for all solutions is $$\sum x_ic_i = m$$. So the value of the smallest coin can be extracted as $$x_0 = \frac{m-\sum_{i>0} x_ic_i}{c_0}$$
This simplifies the system to the weak simplex method with one dimensionless, so one can apply the same recursive formula.
$$f(x,S) = \sum_{y \in S \setminus x_0} f(m-y,S| y \ge m) + (x|m) $$
the scala code for this method is
def change(money: Int, coins: List[Int]) : Int = {
if (money < 0) 0
else if (money == 0) 1
else coins.tail.map(x => change(money-x,coins.filter(y => y<=x))).sum +
(if (money % coins.head == 0) 1 else 0)
}
The time order of this method is $O\left(\frac{m^{n-1}}{n}\right)$
Dynamic programming method
Instead of using the amount of money as a breakdown for our induction, one can use the number of coins as an induction value. If we add a new coin to the set, the number of multisets can be calculated from the old ones. This does not change the recursive formula in any way, but allows us the first calculate all the values for a single coin, if we save these, we can calculate all the values for two coins based on the single one and so on. This means that the runtime of the algorithm is $O(nm)$, which is way faster. (although the runtime is practice is very similar as, even if the recursive tree is exponential, the number branches that are reached are in the same magnitude)
The Scala code is as follows:
def change(money: Int, coins: List[Int]) : Int = {
if (money < 0) return 0
if (coins.isEmpty) return 0
val dp = new Array[Int](money + 1)
dp(0) = 1
var i = 0
while (i < coins.length) {
var j = coins(i)
while (j <= money) {
dp(j) += dp(j - coins(i))
j += 1
}
i += 1
}
return dp(money)
}
Note that if one would clean this code up to be more scala-like, it will reduce itself to a recursive function very similar to the one described above, and less efficient.
Generating function method
It is easy to see that
$$\prod_{c \in S} \sum_{i \rightarrow \infty} x^{ic}$$
Will generate the number of denominations for a specific coin value for each coefficient, independent of the rings over which the polynomial is placed.
This expression can with Taylor series be simplified to
$$\prod_{c \in S} \frac{1}{1-x^{ic}} = (-1)^{\#S} \frac{1}{\prod_{c \in S} x^{ic} - 1}$$
As $$x^a - 1 = \prod_{i=0}^{i<a} x-e^{w_a^i}$$
With $w_a$ the $a$-th root of unity
So if the set $$T = \{ \forall a \in S \forall i < a\}$$
Then our formula simplifies to
$$(-1)^{\#S} \frac{1}{\prod_{c \in T} x - t}$$
This formula can be simplified using partial fraction decomposition.
$$(-1)^{\#S} \sum_{t \in T} \frac{1}{i!(x - t)^{s-i}} \frac{d^i}{dp^i} \frac{(p+t)^s}{\prod_{c \in T} p - c} $$
Where $s$ is the total multiplicity and $i$ is the counting multiplicity.
Complex generating function method
In the complex field, the roots of unity are
$$2\imath \pi/a$$
So we can plug this in in our formula for $T$
Even though the formula looks horrible, it only scales in complexity with the size of $T$, so the speed is $O(ns)$ (with $s$ the size of the largest coin), so for very large amounts (like millions), this formula will be faster.
The main drawback with this method is that small floating points errors propagate enormously(due to all divisions and powers), and as the algorithm runs, these can become larger then 1, and thus give the wrong result, even if the math is correct. This is why we would prefer a field that has no problems from floating-point arithmetic.
Number theory generating function method
Let's take as field the $p$-modulo rings such that $p-1$ is a multiple of all coins. According to the Dirichlet theorem, for every number a prime of the form $kn+1$ exists, so also for the least common multiple of all coins, so this field exists. As $p$ is prime, it as a Primitive root, and all roots of unity can be written as:
$$g^{(p-1)/a}$$ with $g$ the primitive root and $a$ the multiplicity of the root (which is the value of the coin).
The method of partial fractions does not work as derivatives are not defined over this field, but as this field gives a nice linear equation if one uses the method of undetermined coefficients, the problem is actually easier than this.
This algorithm has a slower running time than the above, it is even exponential (as primetest is exponential), but in practice this will run exact and fast for large numbers.
The code will follow in the future.