I’ve built a helper function which I was hoping would use streaming to solve the problem of computing the correct coins to make a given total.
A call to do_generate
will recursively generate all possible combinations, and return them each as {n, map}
where n
is the remaining total, and map
describes the combination of coins used:
iex(4)> Change.do_generate(100, [12, 5, 1]) |> Enum.to_list |> List.first
{0, %{1 => 4, 12 => 8}}
The function is as follows:
def do_generate(amount, []), do: [{amount, %{}}]
def do_generate(amount, [coin | coins]) do
for n <- div(amount, coin)..0,
remaining = amount - n * coin,
{new_amount, map} <- do_generate(remaining, coins),
do: {new_amount, map |> Map.put(coin, n)}
end
If I look at the output from do_generate
in iex
, I see that it’s being fully enumerated:
iex(3)> Change.do_generate(100, [12, 5, 1])
[{0, %{1 => 4, 12 => 8}}, {1, %{1 => 3, 12 => 8}}, {2, %{1 => 2, 12 => 8}},
{3, %{1 => 1, 12 => 8}}, {4, %{1 => 0, 12 => 8}},
[... snip ...]
...]
If I use ~15 coins, the function never returns, because the enumeration is so large. I can get the streaming behaviour I want by changing the second function clause to:
def do_generate(amount, [coin | coins]) do
div(amount, coin)..0
|> Stream.flat_map(fn n ->
remaining = amount - n * coin
do_generate(remaining, coins)
|> Stream.map(fn {new_amount, map} ->
{new_amount, map |> Map.put(coin, n)}
end)
end)
end
iex(2)> Change.do_generate(100, [12, 5, 1])
#Function<57.77324385/2 in Stream.transform/3>
iex(3)> Change.do_generate(100, [12, 5, 1]) |> Enum.at(0)
{0, %{1 => 4, 5 => 0, 12 => 8}}
It surprised me to hit this issue though, because I found some useful information which made me think my two implementations should be equivalent.
I can’t find the mistake I’ve made which is causing the enumeration.