エリクシルの2次元リストの置換

Question

単純なテール再帰を使用して、リストのリストのすべての置換を検索しようとしています。モジュールは次のようになります。再帰は順列の配列がネストされている巻き戻し残念なことにとき

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 

：このため

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 

私のスペックは次のようになります。その仕様の結果は次のとおりです。

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. 

ネスティングを防止する方法についてのヒントはありがたいです。残念なことに、アウトプットを平坦化すると、組み合わせの1次グループも削除されました。

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

次のソリューションは少し珍しいです。

あなたのコードを見ましたが、リストはモナドとして使用でき、通常モナドリストはバックトラックを行うために使用されることを覚えています。 Elixirには、何らかの方法でバックトラッキングを実行するステートメントがあります。forステートメント。あなたの問題を解決するには、次のようなことができます：

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

これは、あなたの例で探している順列のリストを生成します。しかし、それは非常に動的ではありません。私がダイナミックを考えるとき、私は通常、エリクシールのマクロで考える。入力に応じて上記のコードを動的に生成するマクロを作成することができれば、それは理想的でしょう。

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 

私はこれがあなたの問題の解決に役立つことを願っています。上記のコードに関する質問は、私に知らせてください。