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

就我個人而言，最簡單的辦法是扁平化的結果：

def flatten(list, acc \\ []) when is_list(list) do 
    unless list |> Enum.all?(&is_list(&1)) do 
    acC++ [list] 
    else 
    list |> Enum.reduce(acc, fn e, acc -> acC++ flatten(e) end) 
    end 
end 
IO.inspect Permutations.of(list_list, []) |> Permutations.flatten 
#⇒ desired 

因爲這不是標準的扁平化，它應該保持-1嵌套陣列的水平。所有試圖在飛行中展平結果都會打破尾部遞歸。

---

另一種選擇是使用flat_map + chunk：

def of([head | tail], accumulator) do 
    head |> Enum.flat_map(&of(tail, accumulator ++ [&1])) 
end 

IO.inspect Permutations.of(list_list, []) |> Enum.chunk(list_list |> Enum.count) 
#⇒ desired 

Answer 2

下面的解決方案是有點不尋常。

我看到了你的代碼，我記得列表可以用作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 

我希望這可以幫助您解決問題。有關上面的代碼的任何問題，請讓我知道。