So erhalten Sie alle möglichen Kombinationen von Elementen einer Gruppe von Arrays

Ich weiß, dass viele Leute diese Aufgabe googeln, tk. Ich bin kürzlich darauf gestoßen. Da ich nie eine funktionierende Lösung gefunden habe, musste ich mir eine eigene einfallen lassen.



Also die einleitenden Daten. Wir haben eine Gruppe von Arrays, zum Beispiel:

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

Stellen wir uns nun vor, wir müssen eine Reihe von assoziativen Arrays (Map) wie folgt sammeln:

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

In vereinfachter Form sieht der Algorithmus für solche Arbeiten folgendermaßen aus:

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

Jene. Tatsächlich verschachteln wir jede Menge in einer anderen Menge und iterieren darüber in einer Schleife. Jetzt bleibt herauszufinden, wie man dasselbe macht, ohne an eine bestimmte Anzahl von Sätzen gebunden zu sein.



Definieren wir zunächst die Begriffe:



Parameter ist der Name des festgelegten Elements, z. B. Modell, Farbe usw.

Ein Satz von Parameterelementen ist eine Liste, die einem Parameter zugewiesen ist (z. B. ["audi", "bmw", "toyota", "vw"]).

Ein Satzelement ist ein separates Listenelement, z. B. audi, bmw, rot, blau usw.

Ergebnismengen - Was wir generieren sollten



Wie wird es aussehen? Wir brauchen eine Funktion, bei der jeder Aufruf den bedingten Zähler des Iterators, der die Iteration von Parametern (Modell, Farbe usw.) steuert, um eine Position verschiebt. Innerhalb dieser Funktion werden zusätzlich zum Verschieben des Zählers die Elemente des Parameters (audi, bmw ...; rot, blau ... usw.) durchlaufen. Und innerhalb dieser verschachtelten Schleife ruft sich unsere Funktion rekursiv auf.



Das Folgende ist ein Arbeitsbeispiel in Java mit Kommentaren:

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

    }

}