Permutationen einer 2-dimensionalen Liste in Elixir

Question

Ich versuche eine einfache Tail-Rekursion zu verwenden, um alle Permutationen für eine Liste von Listen abzurufen. das Modul sieht wie folgt aus:

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 

für Meine spec wie folgt aussieht:

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 

Leider, wenn die Rekursion die Arrays von Permutationen abwickelt verschachtelt sind. Das Ergebnis dieser Spezifikation ist:

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. 

Ich würde mich über alle Tipps freuen, wie Sie die Verschachtelung verhindern können. Leider hat das Reduzieren der Ausgabe auch die Gruppierung erster Ordnung der Kombinationen entfernt.

Answer 1

Was mich betrifft, so wäre der einfachste Weg, um das Ergebnis zu glätten sein:

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 

Da dies nicht der Standard Abflachung ist, sollte es bleiben -1 Ebene der Verschachtelung Arrays. Alle Versuche, das Ergebnis im Handumdrehen zu reduzieren, würden die Schwanzrekursion unterbrechen.

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

Die folgende Lösung ist ein wenig ungewöhnlich:

---

wäre eine weitere Option flat_map + chunk zu bedienen.

Ich sah Ihren Code und ich erinnere mich, dass Listen als Monad verwendet werden können und in der Regel die Monad-Liste verwendet wird, um Backtracking zu tun. Elixir hat die Anweisung, in irgendeiner Weise Backtracking durchzuführen: die for-Anweisung. Um Ihr Problem zu lösen, können Sie beispielsweise Folgendes tun:

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

Das wird die Liste der Permutationen generieren, die Sie in Ihrem Beispiel suchen. Es ist jedoch nicht sehr dynamisch. Wenn ich an Dynamik denke, denke ich normalerweise an Elixir-Makros. Wenn Sie ein Makro zu erstellen, das den Code oben dynamisch in Abhängigkeit von der Eingabe erzeugt wäre es ideal:

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 

Ich hoffe, das hilft Ihnen, Ihr Problem zu lösen. Irgendwelche Fragen zum obigen Code, lass es mich wissen.