algorithm - Elixir 中二维列表的排列

Question

我正在尝试使用简单的尾递归来检索列表列表的所有排列。该模块如下所示:

defmodule Permutations do

  def of([], accumulator) do
    accumulator
  end

  def of([head | tail], accumulator) do
    for item <- head, do: of(tail, accumulator ++ [item])
  end
end

我对此的规范如下:

defmodule PermutationsSpec do
  use ESpec

  alias WaffleEventImporter.Permutations

  describe "of/2" do
    subject do: Permutations.of(list_list, [])

    let :list_list, do: [[1,2,3],[1,2,3],[1,2,3]]
    let :expected, do: [
      [1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],
      [2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],
      [3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3],
    ]

    it "returns all permutations for the 2 diensional array provided" do
      expect(subject) |> to(eq expected)
    end
  end
end

不幸的是，当递归展开时，排列数组是嵌套的。该规范的结果是:

    Expected `[[[[1, 1, 1], [1, 1, 2], [1, 1, 3]], [[1, 2, 1], [1, 2, 2],
[1, 2, 3]], [[1, 3, 1], [1, 3, 2], [1, 3, 3]]], [[[2, 1, 1], [2, 1, 2], 
[2, 1, 3]], [[2, 2, 1], [2, 2, 2], [2, 2, 3]], [[2, 3, 1], [2, 3, 2], 
[2, 3, 3]]], [[[3, 1, 1], [3, 1, 2], [3, 1, 3]], [[3, 2, 1], [3, 2, 2], 
[3, 2, 3]], [[3, 3, 1], [3, 3, 2], [3, 3, 3]]]]` to equals (==) 
`[[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 1], [1, 2, 2], [1, 2, 3], 
[1, 3, 1], [1, 3, 2], [1, 3, 3], [2, 1, 1], [2, 1, 2], [2, 1, 3], 
[2, 2, 1], [2, 2, 2], [2, 2, 3], [2, 3, 1], [2, 3, 2], [2, 3, 3], 
[3, 1, 1], [3, 1, 2], [3, 1, 3], [3, 2, 1], [3, 2, 2], [3, 2, 3], 
[3, 3, 1], [3, 3, 2], [3, 3, 3]]`, but it doesn't.

如果有任何关于如何防止嵌套的提示，我将不胜感激。不幸的是，扁平化输出也删除了组合的第一顺序分组。

Answer 1

下面的解决方案有点不寻常。

我看过你的代码，我记得列表可以用作 Monad，通常 Monad List 用于回溯。 Elixir 有以某种方式执行回溯的语句:for 语句。要解决您的问题，您可以执行以下操作:

for i <- [1,2,3], j <- [1,2,3], k <- [1,2,3], do: [i, j, k]

这将生成您在示例中查找的排列列表。但是，它不是很有活力。当我想到动态时，我通常会想到 Elixir 宏。如果您可以创建一个根据输入动态生成上述代码的宏，那将是理想的选择:

defmodule Permutation do
  @doc """
  Does the permutations over a list of lists.

  ```
  > require Permutation
  > Permutation.of([[1,2], [1,2]])
  [[1, 1], [1, 2], [2, 1], [2, 2]]
  ```
  """
  defmacro of(list) do
    quote do: unquote(gen(list))
  end

  ##
  # Generates the for statement for the permutation depending on
  # the contents of the input list. Starting index for generated 
  # variables is 0, there are no arrows and the initial result is
  # an empty list.
  @doc false
  def gen(list) do
    gen(list, 0, [], [])
  end

  ##
  # Generates the for statement for the permutation depending on
  # the contents of the input lists.
  defp gen([], _, arrows, list) do
    gen_for(arrows, list)
  end
  defp gen([head | tail], index, arrows, list) when is_list(head) do
    var = gen_var(index)
    arrow = gen_arrow(var, head)
    list = gen_list(var, list)
    gen(tail, index + 1, [arrow | arrows], list)
  end
  defp gen(_, _, _, _) do
    :error
  end

  ##
  # Generates a variable from an index i.e for index 0 generates i0
  defp gen_var(index), do: Macro.var(:"i#{inspect index}", __MODULE__)

  ##
  # Generates an arrow for the for statement i.e. i0 <- [1,2,3]
  defp gen_arrow(var, source) do
    quote do: unquote(var) <- unquote(source)
  end

  ##
  # Generates the list from the for statement block: [i1 | [i0]]
  defp gen_list(var, list) do
    quote do: [unquote(var) | unquote(list)]
  end

  ##
  # Generates the for statement i.e.
  # for i1 <- [1,2,3], i0 <- [1,2,3], do: [i1 | [i0]]
  defp gen_for(arrows, list) do
    quote do
      for unquote_splicing(arrows) do
        unquote(list)
      end
    end
  end
end

希望本文能帮助您解决问题。关于上述代码的任何问题，请告诉我。