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

Автор Сообщение
news_bot ®

Стаж: 6 лет 4 месяца
Сообщений: 27286

Создавать темы news_bot ® написал(а)
16-Авг-2020 20:32

Знаю что эту задачу многие гуглят, т.к. сам недавно столкнулся с этим. Поскольку рабочего решения я так и не нашел, пришлось придумать свое.
Итак, вводные данные. Имеем группу массивов, например:
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);
        }
    }
}

===========
Источник:
habr.com
===========

Похожие новости: Теги для поиска: #_java, #_algoritmy (Алгоритмы), #_kombinatornye_algoritmy (комбинаторные алгоритмы), #_java, #_algoritmy (
Алгоритмы
)
Профиль  ЛС 
Показать сообщения:     

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 06-Июл 11:59
Часовой пояс: UTC + 5