CODEWITHSUNDEEP
javaloopsfor-loopwhile-loop
Harshit Gupta
Harshit Gupta

Reputation: 739

Combination Generator in JAVA

I am trying to find all combinations of items in several arrays. The number of arrays is random (this can be 2, 3, 4, 5...). The number of elements in each array is random too.

e.g., I have the 3 arrays :

String[][] array1 = {{"A1","A2","A3"},{"B1","B2","B3"},{"C1","C2"}};

I would like to generate an array with all possible combinations :

A1, B1, C1
A1, B1, C2
A1, B2, C1
A1, B2, C2
A1, B3, C1
A1, B3, C2
A2, B1, C1
A2, B1, C2 ...

Upvotes: 2

Views: 2291

Answers (2)

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

There are two basic approaches to variable loop nesting. One is explicit bookkeeping, as discussed in the prior answer. The other is a recursive solution. In a recursive solution activations of the recursive method store as local variables the same index data as is tracked in an explicit array in the bookkeeping approach.

The base case for the recursion is to return a length 0 result array if the input contains zero arrays. If the input contains one or more arrays, generate the result from the elements of the first array and the recursive call result for the remaining arrays.

Upvotes: 0

fabian
fabian

Reputation: 82461

You could create the combinations by using a "counter-like" strategy, i.e. treat those arrays as digits of a number like this:

public static String[][] generateCombinations(String[]... arrays) {
    if (arrays.length == 0) {
        return new String[][]{{}};
    }
    int num = 1;
    for (int i = 0; i < arrays.length; i++) {
        num *= arrays[i].length;
    }

    String[][] result = new String[num][arrays.length];

    // array containing the indices of the Strings
    int[] combination = new int[arrays.length];

    for (int i = 0; i < num; i++) {
        String[] comb = result[i];
        // fill array
        for (int j = 0; j < arrays.length; j++) {
            comb[j] = arrays[j][combination[j]];
        }

        // generate next combination
        for (int j = arrays.length-1; j >= 0; j--) {
            int n = ++combination[j];
            if (n >= arrays[j].length) {
                // "digit" exceeded valid range -> back to 0 and continue incrementing
                combination[j] = 0;
            } else {
                // "digit" still in valid range -> stop
                break;
            }
        }
    }
    return result;
}

The method is called like this:

generateCombinations(
            new String[]{"A1","A2","A3"},
            new String[]{"B1","B2","B3"},
            new String[]{"C1","C2"}
       )

or like this:

generateCombinations(array1)

Upvotes: 2

Related Questions