Como obter todas as combinações possíveis de elementos de um grupo de matrizes

Eu sei que muitas pessoas google esta tarefa, tk. Eu mesmo recentemente me deparei com isso. Já que nunca encontrei uma solução que funcionasse, tive que encontrar a minha própria.



Então, os dados introdutórios. Temos um grupo de arrays, por exemplo:



models = [ "audi", "bmw", "toyota", "vw" ];
colors = [ "red", "green", "blue", "yellow", "pink" ];
engines = [ "diesel", "gasoline", "hybrid" ];
transmissions = [ "manual", "auto", "robot" ];


Agora vamos imaginar que precisamos coletar um conjunto de matrizes associativas (mapa) mais ou menos assim:



variant1 = { "model": "audi", "color": "red", "engine": "diesel", "transmission": "manual" }
variant2 = { "model": "audi", "color": "red", "engine": "diesel", "transmission": "auto" }
variant3 = { "model": "audi", "color": "red", "engine": "diesel", "transmission": "robot" }
variant4 = { "model": "audi", "color": "red", "engine": "gasoline", "transmission": "manual" }
variantN = { "model": "vw", "color": "pink", "engine": "hybrid", "transmission": "robot" }


De forma simplificada, o algoritmo para esse trabalho se parece com este:



for(i1 = 0; i1 < models.length; i1 ++){ //  
    for(i2 = 0; i2 < colors.length; i2 ++){ //   
        for(i3 = 0; i3 < engines.length; i3 ++){ //   
            for(i4 = 0; i4 < transmissions.length; i4 ++){ //   
                 variant = {
                      "model": models[i1],
                      "color": colors[i2],
                      "engine": engines[i3],
                      "transmission": transmissions[i4],
                 }
            }
        }
    }
} 


Essa. na verdade, aninhamos cada conjunto dentro de outro conjunto e iteramos sobre ele em um loop. Agora resta descobrir como fazer o mesmo sem estar vinculado a um número específico de conjuntos.



Primeiro, vamos definir os termos:



Parâmetro é o nome do elemento definido, por exemplo, modelo, cor, etc.

Um conjunto de elementos de parâmetro é uma lista atribuída a um parâmetro (por exemplo, ["audi", "bmw", "toyota", "vw"])

Um item definido é um elemento separado de uma lista, por exemplo, audi, bmw, vermelho, azul, etc.

Conjuntos de resultados - o que devemos gerar



Como vai ficar? Precisamos de uma função, cada chamada mudará em uma posição o contador condicional do iterador que controla a iteração de parâmetros (modelo, cor, etc.). Dentro desta função, além de deslocar o contador, itera sobre os elementos do parâmetro (audi, bmw ...; vermelho, azul ... etc.) E dentro desse loop aninhado, nossa função se chamará recursivamente.



A seguir está um exemplo funcional em Java com comentários:



public class App {

    public static void main(String[] args) {
        Map<String, List<String>> source = Map.of(
            "model", Arrays.asList("audy", "bmw", "toyota", "vw"),
            "color", Arrays.asList("red", "green", "blue", "yellow", "pink"),
            "engine", Arrays.asList("diesel", "gasoline", "hybrid"),
            "transmission", Arrays.asList("manual", "auto", "robot")
        );

        Combinator<String, String> combinator = new Combinator<>(source);
        List<Map<String, String>> result = combinator.makeCombinations();

        for(Map variant : result){
            System.out.println(variant);
        }
    }

    public static class Combinator<K,V> {

        //       
        private Map<K, List<V>> sources;

        //   .     
        //ListIterator, ..    previous
        private ListIterator<K> keysIterator;

        //       
        //  -  ,   -     
        private Map<K, Integer> counter;

        //    
        private List<Map<K,V>> result;


        public Combinator(Map<K, List<V>> sources) {
            this.sources = sources;
            counter = new HashMap<>();
            keysIterator = new ArrayList<>(sources.keySet())
                    .listIterator();
        }

        //     
        public List<Map<K,V>> makeCombinations() {
            result = new ArrayList<>();
            //  
            loop();
            return result;
        }

        private void loop(){
            //,      
            if(keysIterator.hasNext()){

                //  
                K key = keysIterator.next();

                //   (  ,
                //     )
                counter.put(key, 0);


                //  
                while(counter.get(key) < sources.get(key).size()){
                    //   loop     
                    loop();

                    //   
                    counter.put(key, counter.get(key) + 1);
                }

                //      -    
                keysIterator.previous();
            }
            else{
                //    , ..     
                //   
                fill();
            }
        }

        //      
        private void fill() {
            Map<K,V> variant = new HashMap<>();

            //  
            for(K key : sources.keySet()){
                //     
                Integer position = counter.get(key);

                //   
                variant.put(key, sources.get(key).get(position));
            }

            result.add(variant);
        }

    }

}



All Articles