Permutations d'une liste bidimensionnelle en elixir

Question

J'essaye d'utiliser une simple récursion de queue pour récupérer toutes les permutations d'une liste de listes. le module ressemble à ceci:

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 

Ma spec pour cela ressemble à:

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 

Malheureusement, lorsque la récursion dévide les tableaux de permutations sont imbriquées. Le résultat de cette spécification est:

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. 

J'apprécierais des conseils sur la façon d'empêcher l'imbrication. Malheureusement, l'aplatissement de la sortie a également supprimé le groupement du premier ordre des combinaisons.

Answer 1

En ce qui me concerne, la meilleure façon serait d'aplatir le résultat:

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 

Puisque ce n'est pas l'aplanissement standard, il devrait rester au niveau -1 de tableaux de nidification. Tout essaie d'aplatir le résultat à la volée pour briser la récursivité de la queue.

---

Une autre option serait d'utiliser 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

La solution suivante est un peu inhabituel.

J'ai vu votre code et je me souviens que les listes peuvent être utilisées comme une Monade et généralement la liste Monad est utilisée pour faire un retour en arrière. Elixir a l'instruction d'effectuer un backtracking d'une façon ou d'une autre: l'instruction for. Pour résoudre votre problème, vous pouvez faire quelque chose comme:

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

Cela va générer la liste des permutations que vous recherchez dans votre exemple. Cependant, ce n'est pas très dynamique. Quand je pense à la dynamique, je pense généralement aux macros Elixir. Si vous pouvez créer une macro qui génère le code ci-dessus dynamiquement en fonction de l'entrée, il serait idéal:

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 

J'espère que cela vous aide à résoudre votre problème. Toute question sur le code ci-dessus, faites le moi savoir.