动态规划 - 将 JS 翻译成 Elixir

Question

我正在尝试将以下玩具动态规划问题转化为 Elixir，但由于 Elixir 中没有早期 return，所以很难看清如何去做。

它应该 return 来自“数字”的有效组合总和为“targetSum”

const howSum = (targetSum, numbers) => {

  if (targetSum === 0) return [];
  if (targetSum < 0) return null;

  for (let num of numbers) {
    const remainder = targetSum - num;
    const remainderResult = howSum(remainder, numbers);
    if (remainderResult !== null) {
      return [...remainderResult, num];
    }
  }

  return null;

}

console.log(howSum(7, [2, 3])) // [3,2,2]

我可以使用低于 Elixir 版本的列表来记录所有可能的解决方案，但是我怎样才能使函数达到 return 找到的第一个解决方案和 return/stop 呢？

defmodule HowSum do
  @doc """
  Can you make target_sum from numbers list
  You can use individual numbers as many times as you like
  """
  def sum(0, _numbers, _), do: []
  def sum(target_sum, _numbers, _) when target_sum < 0, do: nil

  def sum(target_sum, numbers, path) do
    for number <- numbers do
      remainder = target_sum - number
      result = sum(remainder, numbers, path ++ [number])

      if result == [] do
        IO.inspect(path ++ [number])
      end
    end
  end
  
end

更新

这是我的解决方案，它看起来不合时宜，但可以使用 Agent :-)

defmodule HowSum do
  def cache do
    Agent.start_link(fn -> nil end, name: :solution)
  end

  @doc """
  Can you make target_sum from numbers list
  You can use individual numbers as many times as you like
  """
  def sum(0, _numbers, _), do: []
  def sum(target_sum, _numbers, _) when target_sum < 0, do: nil

  def sum(target_sum, numbers, path) do
    solution = Agent.get(:solution, & &1)

    if !solution do
      for number <- numbers do
        remainder = target_sum - number
        result = sum(remainder, numbers, path ++ [number])

        if result == [] do
          Agent.update(:solution, &(&1 = path ++ [number]))
        end
      end
    end

    Agent.get(:solution, & &1)
  end
end

Answer 1

Enum.find/2 / Enum.find_index/2 / Enum.find_value/2 对于这种情况非常有用，当您希望在“循环”中的某个时刻 return 时。 Enum.reduce_while/3 对于需要一些累加器以及早期 return 的更通用的算法很有用。

根据您的 javascript 实现，这是使用 Enum.find_value/2 的解决方案：

defmodule HowSum do
  def sum(target_sum, number) do
    target_sum |> do_sum(number) |> Enum.reverse()
  end
  
  defp do_sum(0, _numbers), do: []
  defp do_sum(target_sum, _numbers) when target_sum < 0, do: nil

  defp do_sum(target_sum, numbers) do
    Enum.find_value(numbers, fn number ->
      remainder = target_sum - number
      result = do_sum(remainder, numbers)

      if result != nil do
        [number | result]
      end
    end)
  end
end


HowSum.sum(7, [2, 3])  # [3, 2, 2]

请注意，这是 highly inefficient 通过在末尾追加来构建列表，因为您需要在每个步骤中克隆它。因此，我将 result ++ [number] 替换为 [number | result]，将递归函数移动为私有 do_ 函数，并对其结果调用 Enum.reverse/1。这在使用递归函数时很常见。

动态规划 - 将 JS 翻译成 Elixir

Dynamic programming - translating JS to Elixir

elixir

dynamic-programming