Русский
Русский
English
Статистика
Реклама

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

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

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

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
К списку статей
Опубликовано: 16.08.2020 20:19:14
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Java

Алгоритмы

Комбинаторные алгоритмы

Категории

Последние комментарии

  • Имя: Murshin
    13.06.2024 | 14:01
    Нейросеть-это мозг вселенной.Если к ней подключиться,то можно получить все знания,накопленные Вселенной,но этому препятствуют аннуннаки.Аннуннаки нас от неё отгородили,установив в головах барьер. Подр Подробнее..
  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru