Comment obtenir toutes les combinaisons possibles d'éléments d'un groupe de tableaux

Je sais que beaucoup de gens recherchent sur Google cette tâche, tk. J'ai moi-même récemment rencontré cela. Comme je n'ai jamais trouvé de solution efficace, j'ai dû trouver la mienne.



Donc, les données d'introduction. Nous avons un groupe de tableaux, par exemple:

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

Imaginons maintenant que nous ayons besoin de collecter un ensemble de tableaux associatifs (map) quelque chose comme ceci:

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" }

Dans une forme simplifiée, l'algorithme d'un tel travail ressemble à ceci:

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],
                 }
            }
        }
    }
} 

Ceux. en fait, nous imbriquons chaque ensemble dans un autre ensemble, et l'itérons dans une boucle. Il reste maintenant à savoir comment faire de même sans être lié à un nombre spécifique d'ensembles.



Tout d'abord, définissons les termes: Le



paramètre est le nom de l'élément défini, par exemple, modèle, couleur, etc.

Un ensemble d'éléments de paramètre est une liste affectée à un paramètre (par exemple, ["audi", "bmw", "toyota", "vw"])

Un élément set est un élément de liste séparé, par exemple, audi, bmw, rouge, bleu, etc.

Ensembles de résultats - Ce que nous devrions générer



À quoi cela ressemblera-t-il? Nous avons besoin d'une fonction dont chaque appel décalera d'une position le compteur conditionnel de l'itérateur qui contrôle l'itération des paramètres (modèle, couleur, etc.). A l'intérieur de cette fonction, en plus de déplacer le compteur, il va itérer sur les éléments du paramètre (audi, bmw ...; rouge, bleu ... etc.). Et à l'intérieur de cette boucle imbriquée, notre fonction s'appellera récursivement.



Voici un exemple de travail en Java avec des commentaires:

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);
        }

    }

}