A popular interview questions involving programming and combinatorics is the *Making a Dollar* problem, Generally stated as follows:

*Making a Dollar* Given unlimited numbers of 1, 5, 10, 25, and 50-cent denomination coin, how many ways are there to make a dollar.

We can count the number of ways to mix the coins into a dollar in two different ways: 1) the biggest denomination is in the mix, and 2) the biggest denomination is not in the mix. If the biggest denomination is in the mix, then let us use one coin of the biggest denomination, and count the number of ways to make the remaining amount using using all available coins. If it is not in the mix, then let us calculate the number of ways to make a dollar using all but the coins of the biggest denomination. Let be the number of ways to make using coins with denominations in , then . This recursive relation needs boundary condition of when the amount to make is less than or equal to zero, and when the set of denominations is empty. These are respectively , , and . The first boundary condition says that we have just a way to make the exact change. The second boundary condition says that we have not been able to found an exact change because the denomination we just used is too large. The last boundary condition says that we have used up all possible denominations and still cannot make the change.

Since I am in the process of learning the Julia language, I decided to code this up using Julia while ignore the issue of efficiency. WordPress does not have syntax highlighting for Julia yet, so…

function const_comb(sum::Int, parts::Array{Int}) if sum == 0 return 1 end if sum < 0 || length(parts) < 1 return 0 end if(n==0 || all(i-> i==0,r)) return 1 else return exp(lfact(n) - sum(lfact(r))); end end

This problem can be slightly generalize this way. Suppose that the order in which the coins are used to make the dollar matters, for example, is different from , then how many ways can we make a dollar? It may seem that we need to keep track of the way we get to the current state and count each way separately. Turns out this is not necessary. We can recycle the algorithm above, but instead of return 1 when we have the the exact change, we return the number of permutations of the . It is easier to model permutation with repetition with a multi-set. A multi-set is a collection of objects that need not be distinct. a multi-set where are non-negative integers and are distinct objects, contains of . From combinatorics theory, the number of ways to form a permutation on a multi-set such that is . Let us first code up the above express for multi-set permutation. Since it involves quite a bit of factorials, special care should be taken to avoid integer overflow.

function nPr(n::Int, r::AbstractArray{Int,1}) if(any(i->i>n, r)) return 0 end if(n==0 || all(i-> i==0,r)) return 1 else return exp(lfact(n) - sum(lfact(r))); end end

Now we simply need to keep track of the multi-set of numbers of coins of each denomination, and count the permutation when we have the exact change or return 0 otherwise. The distinct nature of the objects makes the use of a dictionary in our code a natural choice.

function const_comb_rep(sum::Int, parts::AbstractArray{Int, 1}, multiset::Dict) if sum == 0 return nPr(sum(collect(values(multisite))), collect(values(multiset))) end if sum 0 || length(parts) 1 return 0 end sub_multiset = copy(multiset) if haskey(sub_multiset, parts[end]) sub_multiset[parts[end]] = sub_multiset[parts[end]] + 1 else sub_multiset[parts[end]] = 1 end return const_comb_rep(sum - parts[end], parts, sub_multiset) + const_comb_rep(sum, parts[1:end-1], multiset) end

where line 5 should be `sum < 0 || length(parts) < 1`

where for some very bizarre reasons WordPress just cannot render correctly and have cost me several hours to finally give up trying.

running with some test input get

const_comb_rep(7, [1, 2, 3], Dict()) 44.0 [const_comb_rep(n,1:n, Dict{Int,Int}()) for n = 1:10] 10-element Array{Union{Float64,Int64},1}: 1.0 2.0 4.0 8.0 16.0 32.0 64.0 128.0 256.0 512.0

Here the multi-set is modelled as a dictionary with keys being the distinct object and value being the number of object. As we recurse, the dictionary keeps tract of the number and denomination of the coins used. Finally when we have an exact change, the number of ways to arrange them is computed and returned back.

Note that the number of ways to make Integer using numbers from is .

Of course, in real life one does not care the order of which changes are returned to make up the right amount. The problem is perhaps more suitable to the pave a road problem:

* Paving a Road* Find the number of ways to pave a block of road using , , and blocks, assuming each block is indistinguishable.

The above algorithm gives 44 ways, and one can actually print out each way if one add a print command inside the if sum == 0 statement.