Как получить все возможные комбинации элементов группы массивов

Знаю что эту задачу многие гуглят, т.к. сам недавно столкнулся с этим. Поскольку рабочего решения я так и не нашел, пришлось придумать свое.

Итак, вводные данные. Имеем группу массивов, например:

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

Теперь представим, что нам надо собрать набор ассоциативных массивов (map) примерно такого вида:

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

В упрощенном виде алгоритм подобной работы выглядит так:

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

Т.е. по сути вкладываем каждый набор внутрь другого набора, и перебираем в цикле. Теперь остается придумать как сделать то-же самое без привязки к конкретному числу наборов.

Для начала определимся с терминами:

Параметр — то, как называется элемент набора, например model, color и т.д.
Набор элементов параметра — список, присвоенный параметру (например, [ «audi», «bmw», «toyota», «vw» ])
Элемент набора — отдельный элемент списка, например audi, bmw, red, blue и т.п.
Итоговые наборы — то что мы должны сгенерировать

Как это будет выглядеть? Нам потребуется функция, при каждом вызове которой будет сдвигаться на одну позицию условный счетчик итератора, контролирующего перебор параметров (model, color и т.п.). Внутри этой функции помимо сдвига счетчика будет проходить перебор элементов параметра (audi, bmw…; red, blue… и т.д.). И внутри этого вложенного цикла наша функция будет рекурсивно вызывать сама себя.

Далее рабочий пример на языке Java с комментариями:

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