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.