[Java, Алгоритмы] Как получить все возможные комбинации элементов группы массивов
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Знаю что эту задачу многие гуглят, т.к. сам недавно столкнулся с этим. Поскольку рабочего решения я так и не нашел, пришлось придумать свое.
Итак, вводные данные. Имеем группу массивов, например:
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
===========
Похожие новости:
- [Разработка веб-сайтов, JavaScript] Веб-компоненты в реальном мире (часть 2)
- [PHP, Алгоритмы, HTML] Как я html-парсер на php писал, и что из этого вышло. Заключительная часть
- [JavaScript] LINQ на JavaScript для самых маленьких
- [Разработка веб-сайтов, JavaScript, Программирование, Node.JS] Краткое руководство по Node.js для начинающих (SPA, PWA, mobile-first)
- [Java, Delphi] JNI и Delphi. Использование Java методов при помощи JNI
- [Разработка веб-сайтов, JavaScript, Java, VueJS] Знакомство с Vuecket
- [JavaScript, Node.JS, ReactJS, VueJS] Что, черт возьми, такое гидратация и регидратация? (перевод)
- [Разработка веб-сайтов, JavaScript, Программирование] JavaScript: 250+ практических вопроса (список + викторина + бонус)
- [C, Алгоритмы, Программирование микроконтроллеров] stm32. Смотрим в корень
- [Java] Ах, эти строки
Теги для поиска: #_java, #_algoritmy (Алгоритмы), #_kombinatornye_algoritmy (комбинаторные алгоритмы), #_java, #_algoritmy (
Алгоритмы
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 16:11
Часовой пояс: UTC + 5
Автор | Сообщение |
---|---|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
Знаю что эту задачу многие гуглят, т.к. сам недавно столкнулся с этим. Поскольку рабочего решения я так и не нашел, пришлось придумать свое. Итак, вводные данные. Имеем группу массивов, например: 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 =========== Похожие новости:
Алгоритмы ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 16:11
Часовой пояс: UTC + 5