У меня есть два массива:
String[] operators = {"+", "-", "*"};
int[] numbers = {48, 24, 12, 6};
И я хочу получить все возможные комбинации в формате String, как это:
48+24+12+6
48+24+12-6
48+24+12*6
48+24-12+6
48+24-12-6
48+24-12*6
..........
48*24*12*6
Вот что я попробовал:
for(int i = 0; i < operators.length; i++) {
System.out.println(numbers[0] + operators[i] + numbers[1] + operators[i] + numbers[2] + operators[i] + numbers[3]);
}
Но это только печатает:
48+24+12+6
48-24-12-6
48*24*12*6
Как это решить?
Это не дубликат, потому что я не хочу получать каждые две пары данных, я хочу получить каждую комбинацию в 4 парах. Дубликат отличается.
Используйте тройной цикл:
for (int i=0; i < operators.length; ++i) {
for (int j=0; j < operators.length; ++j) {
for (int k=0; k < operators.length; ++k) {
System.out.println(numbers[0] + operators[i] + numbers[1] + operators[j] +
numbers[2] + operators[k] + numbers[3]);
}
}
}
По сути, вы хотите взять кросс-произведение вектора операторов (если бы оно было вектором). В Java это переводится в тройной набор циклов.
Хотя решение @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<r; j++)
System.out.print(data[j]+" ");
System.out.println("");
return;
}
// 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);
}
Источник: GeeksForGeeks и моя IDE :)
Это похоже на случай учебника для рекурсивного решения:
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 = {"48", "24", "12", "6"};
combineAndPrint(numbers, operators);
}
Кстати, чтобы обобщить этот метод, чтобы вы могли делать больше вещей с сгенерированными выражениями, чем просто печатать их, я бы рекомендовал сделать так, чтобы он принимал дополнительный параметр Consumer<String>. То есть вы можете переписать объявление метода следующим образом:
public static void combine(String[] pieces, String[] operators, Consumer<String> 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 уже есть, и тогда нам даже не нужно будет больше обгонять потребителя.)
Я сделал альтернативное, сверхинженерное (но гибкое!) "Бизнес" решение. Длина и значения массива (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 = {48, 24, 12, 6};
ArrayList<String> strings = new MainClass().getAllPossibleCombinations(numbers, operators);
for (String string : strings)
{
System.out.println(string);
}
}
private ArrayList<String> 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");
ArrayList<String> returnList = 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);
}
}
Работает как шарм :)
Как уже указывал 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 = {48, 24, 12, 6};
CombinationIterable<String> iterable =
new CombinationIterable<String>(3, Arrays.asList(operators));
for (List<String> element : iterable)
{
System.out.println(interveave(element, numbers));
}
}
private static String interveave(List<String> operators, int numbers[])
{
StringBuilder sb = new StringBuilder();
for (int i=0; i<operators.size(); i++)
{
sb.append(numbers[i]);
sb.append(operators.get(i));
}
sb.append(numbers[numbers.length-1]);
return sb.toString();
}
}
class CombinationIterable<T> implements Iterable<List<T>>
{
private final List<T> input;
private final int sampleSize;
private final int numElements;
public CombinationIterable(int sampleSize, List<T> input)
{
this.sampleSize = sampleSize;
this.input = input;
numElements = (int) Math.pow(input.size(), sampleSize);
}
@Override
public Iterator<List<T>> iterator()
{
return new Iterator<List<T>>()
{
private int current = 0;
private final int chosen[] = new int[sampleSize];
@Override
public boolean hasNext()
{
return current < numElements;
}
@Override
public List<T> next()
{
if (!hasNext())
{
throw new NoSuchElementException("No more elements");
}
List<T> result = new ArrayList<T>(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 может быть связан. Но вопрос о том, следует ли рассматривать такие вещи, как ассоциативность или коммутативность, здесь не упоминался.
Немного справочной информации, почему ответы такие, какие они есть. Эта проблема на самом деле не называется "все возможные комбинации", так как обычно это проблема, когда вы можете представлять элементы в виде битов и переключать их на 0 или 1, независимо от того, включен элемент или нет. Это имеет сложность 2 ^ N, где N - количество операторов, которые у вас есть. Это можно легко решить за один цикл.
Однако в вашем случае у вас есть "проблема урны с заменой и последовательностью". Сложность этого заключается в N ^ n, где n - количество мест, которые вы должны заполнить операторами. (Это часто наблюдается для пин-кодов, где каждое пятно может иметь 10 значений). Таким образом, поскольку это более сложная задача, чем проблема "всех возможных комбинаций", вам нужно несколько циклов или рекурсивных вызовов.
Итак, чтобы ответить на вопрос "как это решить?". Вы должны решить это с помощью нескольких циклов или рекурсии из-за основной сложности проблемы.
Вам не нужно многократные циклы или рекурсия.
Вот пример, демонстрирующий ограниченное количество циклов и никакой рекурсии.
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[]{1, 2, 3});
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]