How to get all possible combinations from two arrays?

Question

I have the two arrays:

String[] operators = {"+", "-", "*"};
int[] numbers = {48, 24, 12, 6};

And I want to get all possible combination in a String format like this:

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

This what I have tried:

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]);
}

But it only prints:

48+24+12+6
48-24-12-6
48*24*12*6

How to solve this?

This is not a duplicate because I don't want to get every two pairs of data, I want to get every combination in 4 pairs. The duplicate is different.

Anteroom

Answer 1

Use a triple loop:

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]);
        }
    }
}

You essentially want to take the cross product of the operators vector (if it were a vector). In Java, this translates to a triply-nested set of loops.

Ascarid

Answer 2

While @TimBiegeleisen solution would work like a charm, its complexity might be an issue. The better approach would be a code like this:

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);
}

Source: GeeksForGeeks and my IDE :)

Adventurism

Answer 3

This sounds like a textbook case for a recursive solution:

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's 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);
}

Try it online!

BTW, to generalize this method so that you can do more things with the generated expressions than just printing them, I would recommend making it accept an extra Consumer<String> parameter. That is, you could rewrite the method declaration as:

public static void combine(String[] pieces, String[] operators, Consumer<String> consumer) {

and replace the System.out.println(pieces[0]) with consumer.accept(pieces[0]) and the recursive call to combineAndPrint(newPieces, operators) with combine(newPieces, operators, consumer). Then just call it from your main method e.g. as:

combine(numbers, operators, s -> System.out.println(s));

Try it online!

(Of course, doing it in this more flexible way requires a somewhat modern Java version — Java 8 or later, to be specific — whereas the first example I showed above should work on even ancient versions all the way down to Java 1.0. Maybe in some future version of Java we'll get proper support for coroutines and generators, like Python and Kotlin and even modern JS already have, and then we won't even need to pass the consumer around any more.)

Fates

Answer 4

I made an alternative, overengineered (but flexible!) "business" solution. The array lengths and values (numbers and operators) can be flexible.

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);
    }
}

Works like a charm :)

Sapers

Answer 5

As already pointed out by findusl in his answer, the problem here is, strictly speaking, not to find any sort of "combination of two arrays". Instead, you basically just want to find all possible combinations of the available operators.

(The fact that you later want to "interveave" them with operands is rather unrelated to the core of the question)

So here is another option for solving this: You can create an iterable over all combinations of a certain number of elements from a certain set (in your case: the operators) and then simply combine the results with the other set (in your case: the operands).

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--;
                }
            }
        };
    }
}

---

The task resembles that of finding a set of operations that can be done with a certain number of operands and operators, and thus, this Q/A may be related. But whether or not things like associativity or commutativity should be considered here was not mentioned in the question.

Mix

Answer 6

A bit of background information why the answers are they way they are. This problem is not really called "all possible combinations" as that is usually the problem where you can represent the elements as bits and switch them to 0 or 1 whether the element is included or not. This has a complexity of 2^N where N is the amount of operators you have. This can be solved easily in a single loop.

However in your case you have the "urn problem with replacement and sequence". The complexity of this is N^n where n is the amount of spots you have to fill with operators. (This is often seen for pincodes where each spots can be 10 values). So because this is of higher complexity than the "all possible combinations" problem you need multiple loops or recursive calls.

So to answer the question, "how to solve this?". You have to solve it with multiple loops or recursion because of the underlying problem's complexity.

Katabatic

Answer 7

You don't need multiple loops or recursion.

Here's an example showcasing a limited number of loops and no recursion at all.

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;
}

If you use it with three elements, [1, 2, 3], as in the code below:

void testCombine() {
    int[][] combinations = combine(new int[]{1, 2, 3});
    for (int[] combination : combinations) {
        System.out.println(Arrays.toString(combination));
    }
}

You end up with the following result:

[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]

Picard

Answer 8

I've developed a class that covers this use case and many others. I call it the TallyCounter. Your question would be answered with this class like this:

package app;

import java.util.HashMap;
import java.util.Map;

import app.TallyCounter.Type;

public class App {
    public static void main(String args[]) throws Exception {
        Map<Long, String> map = new HashMap<>();
        map.put(0l, "+");
        map.put(1l, "-");
        map.put(2l, "*");

        TallyCounter counter = new TallyCounter(3, Type.NORMAL, 2);
        do {
            System.out.format("48%s24%s12%s6\n",
                    map.get(counter.getArray()[2]),
                    map.get(counter.getArray()[1]),
                    map.get(counter.getArray()[0])
            );
            counter.increment();
        } while (!counter.overflowFlag);
    }
}

Worldly

Answer 9

You can use streams to get all possible combinations of two arrays. First, iterate over the numbers array and append the operator signs to each number, you get an array like this: {"48+", "48-", "48*"} for each number. The number of operators may vary. Then reduce this stream of arrays to a single array by sequentially multiplying array pairs, you get an array of possible combinations.

Try it online!

String[] operators = {"+", "-", "*"};
int[] numbers = {48, 24, 12, 6};

// an array of possible combinations
String[] comb = IntStream.range(0, numbers.length)
        // append each substring with possible
        // combinations, except the last one
        // return Stream<String[]>
        .mapToObj(i -> numbers.length - 1 > i ?
                Arrays.stream(operators)
                        .map(op -> numbers[i] + op)
                        .toArray(String[]::new) :
                new String[]{"" + numbers[i]})
        // reduce stream of arrays to a single array
        // by sequentially multiplying array pairs
        .reduce((arr1, arr2) -> Arrays.stream(arr1)
                .flatMap(str1 -> Arrays.stream(arr2)
                        .map(str2 -> str1 + str2))
                .toArray(String[]::new))
        .orElse(null);

---

// column-wise output (three columns in this case)
int columns = (int) Math.pow(operators.length, numbers.length - 2);
IntStream.range(0, columns)
        .mapToObj(i -> IntStream.range(0, comb.length)
                .filter(j -> j % columns == i)
                .mapToObj(j -> comb[j])
                .collect(Collectors.joining(" | ")))
        .forEach(System.out::println);

Output:

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 | 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 | 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
48+24*12-6 | 48-24*12-6 | 48*24*12-6
48+24*12*6 | 48-24*12*6 | 48*24*12*6

---

^{See also: Generate all possible string combinations by replacing the hidden “#” number sign}

Diction