How to get all possible combinations of elements of a group of arrays

I know that many people google this task, tk. myself recently encountered this. Since I never found a working solution, I had to come up with my own.



So, the introductory data. We have a group of arrays, for example:

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

Now let's imagine that we need to collect a set of associative arrays (map) something like this:

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 a simplified form, the algorithm for such work looks like this:

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

Those. in fact, we nest each set inside another set, and iterate over it in a loop. Now it remains to figure out how to do the same without being bound to a specific number of sets.



First, let's define the terms:



Parameter is the name of the set element, for example, model, color, etc.

A set of parameter elements is a list assigned to a parameter (for example, ["audi", "bmw", "toyota", "vw"])

A set item is a separate element of a list, for example, audi, bmw, red, blue, etc.

Result Sets - What We Should Generate



How will it look like? We need a function, each call of which will shift by one position the conditional counter of the iterator that controls the iteration of parameters (model, color, etc.). Inside this function, in addition to shifting the counter, it will iterate over the elements of the parameter (audi, bmw ...; red, blue ... etc.). And inside this nested loop, our function will recursively call itself.



The following is a working example in Java with comments:

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

    }

}