Как получить все возможные комбинации из двух массивов в Java?
Как это решить? Это не дубликат, потому что я не хочу получать каждые две пары данных, я хочу получить каждую комбинацию в 4 парах. Дубликат отличается.
7 ответов
По сути, вы хотите взять кросс-произведение вектора операторов (если бы оно было вектором). В Java это переводится в тройной набор циклов.
Чтобы ответить всем: Java не ориентирован на данные. Честно говоря, если вам нужны такие манипуляции в долгосрочной перспективе, то, возможно, вам следует работать в R или Matlab, где можно сформулировать более общее решение без явных циклов.
Вы ссылаетесь на математическое уравнение / операцию, которая может быть использована для решения этой проблемы. Не могли бы вы уточнить это или хотя бы показать уравнение в явном виде?
Это основано на очевидном совпадении того, что число определенных операторов совпадает с количеством позиций для операторов (т.е. на одно число меньше, чем число). Если они не гарантированы, тогда нужно совершенно другой подход.
Хотя решение @TimBiegeleisen будет работать как шарм, его сложность может быть проблемой. Лучшим подходом был бы такой код:
static void combinationUtil(int[] arr, int n, int r, int index, int[] data, int i) < // Current combination is ready to be printed, print it if (index == r) < for (int j=0; j// When no more elements are there to put in data[] if (i >= n) return; // current is included, put next at next location data[index] = arr[i]; combinationUtil(arr, n, r, index+1, data, i+1); // current is excluded, replace it with next (Note that // i+1 is passed, but index is not changed) combinationUtil(arr, n, r, index, data, i+1); > // The main function that prints all combinations of size r // in arr[] of size n. This function mainly uses combinationUtil() static void printCombination(int arr[], int n, int r) < // A temporary array to store all combination one by one int data[]=new int[r]; // Print all combination using temprary array 'data[]' combinationUtil(arr, n, r, 0, data, 0); >Стоит отметить, что у рекурсии есть свои проблемы: слишком много итераций, и вы получите StackOverflowException
Небольшое дополнение, но предпочитаю записывать скобки массива перед именем и после типа: int[] data а не стиль int data[]
@DavidLavender, да, но с рекурсией в этом коде я не думаю, что будут проблемы с довольно большими числами.
@DavidLavender Если бы массив был достаточно длинным для переполнения стека, вывод был бы слишком велик для этой вселенной.
Это похоже на случай учебника для рекурсивного решения:
public static void combineAndPrint(String[] pieces, String[] operators) < if (pieces.length < 1) < // no pieces? do nothing! >else if (pieces.length == 1) < // just one piece? no need to join anything, just print it! System.out.println(pieces[0]); >else < // make a new array that one piece shorter String[] newPieces = new String[pieces.length - 1]; // copy all but the first two pieces into it for (int i = 2; i < pieces.length; i++) < newPieces[i - 1] = pieces[i]; >// combine the first two pieces and recurse for (int i = 0; i < operators.length; i++) < newPieces[0] = pieces[0] + operators[i] + pieces[1]; combineAndPrint(newPieces, operators); >> > public static void main(String[] args) < String[] operators = ; String[] numbers = ; combineAndPrint(numbers, operators); > Кстати, чтобы обобщить этот метод, чтобы вы могли делать больше вещей с сгенерированными выражениями, чем просто печатать их, я бы рекомендовал сделать так, чтобы он принимал дополнительный параметр Consumer . То есть вы можете переписать объявление метода следующим образом:
public static void combine(String[] pieces, String[] operators, Consumer consumer) и замените System.out.println(pieces[0]) на combineAndPrint(newPieces, operators) consumer.accept(pieces[0]) и рекурсивный вызов функции combineAndPrint(newPieces, operators) с combine(newPieces, operators, consumer) . Затем просто вызовите его из основного метода, например:
combine(numbers, operators, s -> System.out.println(s)); (Конечно, для того, чтобы сделать это более гибким способом, требуется более современная версия Java - точнее, Java 8 или новее - тогда как первый пример, который я показал выше, должен работать даже на древних версиях вплоть до Java 1.0. В какой-то будущей версии Java мы получим надлежащую поддержку сопрограмм и генераторов, таких как Python и Kotlin, и даже современные JS уже есть, и тогда нам даже не нужно будет больше обгонять потребителя.)
@IlmariKaronen Не правильнее ли повторять, начиная с 1, а не с 2? for (int i = 1; i < pieces.length; i++)
@OlegCaralanski: Мы хотим скопировать все, кроме первых двух элементов pieces в newPieces , оставив первый слот newPieces свободным для комбинации первых двух элементов pieces . Мы можем сделать это с помощью либо for (int i = 2; i < pieces.length; i++) newPieces[i - 1] = pieces[i]; или for (int i = 1; i < newPieces.length; i++) newPieces[i] = pieces[i + 1]; , В любом случае работает. (Конечно, это также ничего не сломало бы, если бы мы начали цикл за один элемент ранее, но тогда мы будем делать бесполезную работу, копируя pieces[1] в newPieces[0] только для того, чтобы они были перезаписаны ниже.)
Я сделал альтернативное, сверхинженерное (но гибкое!) "Бизнес" решение. Длина и значения массива ( numbers и operators ) могут быть гибкими.
package test1; import java.io.IOException; import java.util.ArrayList; public class MainClass < public static void main(String[] args) throws IOException < String[] operators = ; int[] numbers = ; ArrayList strings = new MainClass().getAllPossibleCombinations(numbers, operators); for (String string : strings) < System.out.println(string); >> private ArrayList getAllPossibleCombinations(int[] numbers, String[] operators) < if (numbers.length < 2) throw new IllegalArgumentException("Length of numbers-array must be at least 2"); if (operators.length < 1) throw new IllegalArgumentException("Length of operators-array must be at least 1"); ArrayListreturnList = new ArrayList<>(); int[] indexes = new int[numbers.length - 1]; while (true) < StringBuilder line = new StringBuilder(); for (int i = 0; i < numbers.length; i++) < int number = numbers[i]; line.append(number); if (i < indexes.length) < line.append(operators[indexes[i]]); >> returnList.add(line.toString()); try < this.updateIndexes(indexes, operators.length - 1); >catch (NoMoreCombinationsException e) < break; >> return returnList; > private void updateIndexes(int[] currentIndexes, int maxValue) throws NoMoreCombinationsException < if (this.intArrayIsOnly(currentIndexes, maxValue)) < throw new NoMoreCombinationsException(); >for (int i = currentIndexes.length - 1; i >= 0; i--) < int currentIndex = currentIndexes[i]; if (currentIndex < maxValue) < currentIndexes[i] = currentIndex + 1; break; >else < currentIndexes[i] = 0; >> > private boolean intArrayIsOnly(int[] array, int value) < for (int iteratedValue : array) < if (iteratedValue != value) return false; >return true; > > class NoMoreCombinationsException extends Exception < public NoMoreCombinationsException() < >public NoMoreCombinationsException(String message) < super(message); >public NoMoreCombinationsException(String message, Throwable cause) < super(message, cause); >public NoMoreCombinationsException(Throwable cause) < super(cause); >public NoMoreCombinationsException(String message, Throwable cause, boolean enableSuppression, boolean writableStackTrace) < super(message, cause, enableSuppression, writableStackTrace); >> Я бы не назвал это printAllPossible . Этот метод на самом деле ничего не печатает. Может генерировать.
Вы можете упростить это . Сделайте ваши методы статичными и верните boolean в updateIndexes . Избегайте использования исключений в управлении потоком данных; и отдавайте предпочтение интерфейсу List вместо реализации ArrayList в ваших API.
Как уже указывал findusl в своем ответе, проблема здесь, строго говоря, не в том, чтобы найти какую-либо "комбинацию двух массивов". Вместо этого вы просто хотите найти все возможные комбинации доступных операторов.
(Тот факт, что вы позже захотите "перемешать" их с операндами, скорее не имеет отношения к сути вопроса)
Итак, вот еще один вариант решения этой проблемы: вы можете создать итерацию по всем комбинациям определенного количества элементов из определенного набора (в вашем случае: операторы), а затем просто объединить результаты с другим набором (в вашем случае: операнды).
import java.util.ArrayList; import java.util.Arrays; import java.util.Iterator; import java.util.List; import java.util.NoSuchElementException; public class OperatorsTest < public static void main(String[] args) < String[] operators = ; int[] numbers = ; CombinationIterable iterable = new CombinationIterable(3, Arrays.asList(operators)); for (List element : iterable) < System.out.println(interveave(element, numbers)); >> private static String interveave(List operators, int numbers[]) < StringBuilder sb = new StringBuilder(); for (int i=0; isb.append(numbers[numbers.length-1]); return sb.toString(); > > class CombinationIterable implements Iterable < private final Listinput; private final int sampleSize; private final int numElements; public CombinationIterable(int sampleSize, List input) < this.sampleSize = sampleSize; this.input = input; numElements = (int) Math.pow(input.size(), sampleSize); >@Override public Iterator iterator() < return new Iterator() < private int current = 0; private final int chosen[] = new int[sampleSize]; @Override public boolean hasNext() < return current < numElements; >@Override public List next() < if (!hasNext()) < throw new NoSuchElementException("No more elements"); >List result = new ArrayList(sampleSize); for (int i = 0; i < sampleSize; i++) < result.add(input.get(chosen[i])); >increase(); current++; return result; > private void increase() < int index = chosen.length - 1; while (index >= 0) < if (chosen[index] < input.size() - 1) < chosen[index]++; return; >chosen[index] = 0; index--; > > >; > >
Задача напоминает задачу поиска набора операций, которые могут быть выполнены с определенным количеством операндов и операторов, и, таким образом, этот Q/A может быть связан. Но вопрос о том, следует ли рассматривать такие вещи, как ассоциативность или коммутативность, здесь не упоминался.
Вам не нужно многократные циклы или рекурсия.
Вот пример, демонстрирующий ограниченное количество циклов и никакой рекурсии.
int[][] combine (int[] values) < int size = values.length; int combinations = 1; for(int i = 0; i < size; i++) < combinations *= size; >// or int combinations = (int)Math.pow(size, size); int[][] result = new int[combinations][size]; for(int i = 0; i < combinations; i++) < int index = i; for(int j = 0; j < size; j++) < result[i][j] = values[index % size]; index /= size; >> return result; > Если вы используете его с тремя элементами, [1, 2, 3] , как в коде ниже:
void testCombine() < int[][] combinations = combine(new int[]); for(int[] combination: combinations) < System.out.println(Arrays.toString(combination)); >> В итоге вы получите следующий результат:
[1, 1, 1] [2, 1, 1] [3, 1, 1] [1, 2, 1] [2, 2, 1] [3, 2, 1] [1, 3, 1] [2, 3, 1] [3, 3, 1] [1, 1, 2] [2, 1, 2] [3, 1, 2] [1, 2, 2] [2, 2, 2] [3, 2, 2] [1, 3, 2] [2, 3, 2] [3, 3, 2] [1, 1, 3] [2, 1, 3] [3, 1, 3] [1, 2, 3] [2, 2, 3] [3, 2, 3] [1, 3, 3] [2, 3, 3] [3, 3, 3] Как получить все возможные комбинации элементов группы массивов
Знаю что эту задачу многие гуглят, т.к. сам недавно столкнулся с этим. Поскольку рабочего решения я так и не нашел, пришлось придумать свое.
Итак, вводные данные. Имеем группу массивов, например:
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, 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> 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 combinator = new Combinator<>(source); List