Example: Coin Changes for Fun

Let S be a finite set of positive numbers. The problem we want to solve is to find out the number of distinct ways for a given integer x to be expressed as the sum of multiples of the positive numbers chosen from S. If we interpret each number in S as the denomination of a coin, then the problem asks how many distinct ways there exist for a given value x to be expressed as the sum of a set of coins. If we use cc(S, x) for this number, then we have the following properties on the function cc:

In the following implementation, we fix S to be the set consisting of 1, 5, 10 and 25.

// typedef int4 = (int, int, int, int) // val theCoins = (1, 5, 10, 25): int4 // fun coin_get (n: int): int = ( if n = 0 then theCoins.0 else if n = 1 then theCoins.1 else if n = 2 then theCoins.2 else if n = 3 then theCoins.3 else ~1 (* erroneous value *) ) (* end of [coin_get] *) // fun coin_change (sum: int): int = let fun aux (sum: int, n: int): int = if sum > 0 then (if n >= 0 then aux (sum, n-1) + aux (sum-coin_get(n), n) else 0) else (if sum < 0 then 0 else 1) // end of [aux] in aux (sum, 3) end // end of [coin_change] //

The auxiliary function aux defined in the body of the function coin_change corresponds to the cc function mentioned above. When applied to 1000, the function coin_change returns 142511.

Note that the entire code in this section plus some additional code for testing is available on-line.