Итак, вводные данные. Имеем группу массивов, например:
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); } }}
