Print combinations of strings in a 2D jagged array

Question

Say I have an array of strings that look like:

{{"blue", "red"}, {"1", "2", "3"}, {"dog", "cat", "fish", "bird"}}

I want to print the combinations of the arrays:

blue 1 dog
blue 1 cat
...
...
red 3 bird

However I want the jagged array to have rows and column that are user specified. How can I create a similar approach but in a dynamic and iterative way? Also I'm working with arrays and not ArrayList because as a beginner I want to see what I can do with arrays before learning ArrayList. My code is below:

Scanner input = new Scanner(System.in);
System.out.print("Enter number of arrays: ");
int arrays = input.nextInt();
String[][] array = new String[arrays][];

for (int i = 0; i < x; i++) {
    System.out.print("Enter number of elements for array: ");
    int elements = input.nextInt();
    input.nextLine();
    arrays[i] = new String[elements];

    for (int j = 0; j < elements; j++) {
        System.out.print("Enter string: ");
        String word = input.nextLine();
        arrays[i][j] = word;
    }
}

Answer 1

This answer will print all combinations, without use of recursion, but will fail if the total number of combinations exceeds Long.MAX_VALUE. Since printing that many lines would never end anyway, that's not really a problem.

To print combinations in order, think of an incrementing number, where each digit of the number is an index into the corresponding sub-list.

Examples (using list of list from question):

000: blue 1 dog
001: blue 1 cat
002: blue 1 fish
003: blue 1 bird
010: blue 2 dog
...
121: red 3 cat
122: red 3 fish
123: red 3 bird

Each "digit" will roll over when it reaches end of corresponding sublist, e.g. last sublist only has 4 elements, so digit rolls over from 3 to 0.

Note: A "digit" can count higher than 9. Think hex for one way to represent that.

Now, the number of digits is dynamic too, i.e. the size of the outer list. One way to do this with simple loops, is to calculate the total number of combinations (2 * 3 * 4 = 24), then calculate the digits using division and remainder.

Example:

Combination #10 (first combination is #0):
  10 % 4                 = 2 (last digit)
  10 / 4 % 3     = 2 % 3 = 2 (middle digit)
  10 / 4 / 3 % 2 = 0 % 2 = 0 (first digit)
  Digits: 022 = blue 3 fish

To help with this, we first build an array of divisors, e.g. div[] = { 12, 4, 1 }, and find the total number of combinations (24).

long[] div = new long[array.length];
long total = 1;
for (int i = array.length - 1; i >= 0; i--) {
    div[i] = total;
    if ((total *= array[i].length) <= 0)
        throw new IllegalStateException("Overflow or empty sublist");
}

Now we can loop through the combinations and print the result:

for (long combo = 0; combo < total; combo++) {
    for (int i = 0; i < array.length; i++) {
        int digit = (int) (combo / div[i] % array[i].length);
        if (i != 0)
            System.out.print(' ');
        System.out.print(array[i][digit]);
    }
    System.out.println();
}

With input from question:

String[][] array = {{"blue", "red"}, {"1", "2", "3"}, {"dog","cat", "fish", "bird"}};

We get the following output:

blue 1 dog
blue 1 cat
blue 1 fish
blue 1 bird
blue 2 dog
blue 2 cat
blue 2 fish
blue 2 bird
blue 3 dog
blue 3 cat
blue 3 fish
blue 3 bird
red 1 dog
red 1 cat
red 1 fish
red 1 bird
red 2 dog
red 2 cat
red 2 fish
red 2 bird
red 3 dog
red 3 cat
red 3 fish
red 3 bird

It can handle any combination of sub-arrays, e.g. with 4 sub-arrays of sizes 2, 3, 2, and 2:

String[][] array = {{"small", "large"}, {"black", "tan", "silver"}, {"lazy", "happy"}, {"dog", "cat"}};

small black lazy dog
small black lazy cat
small black happy dog
small black happy cat
small tan lazy dog
small tan lazy cat
small tan happy dog
small tan happy cat
small silver lazy dog
small silver lazy cat
small silver happy dog
small silver happy cat
large black lazy dog
large black lazy cat
large black happy dog
large black happy cat
large tan lazy dog
large tan lazy cat
large tan happy dog
large tan happy cat
large silver lazy dog
large silver lazy cat
large silver happy dog
large silver happy cat

Answer 2

Here's another approach that uses an array of integer indices to simulate a variable number of nested for loops:

Scanner input = new Scanner(System.in);
System.out.print("Enter number of arrays: ");
int arrays = input.nextInt();
String[][] array = new String[arrays][];

for (int i = 0; i < arrays; i++) {
    System.out.print("Enter number of elements for array #" + i + ": ");
    int elements = input.nextInt();
    input.nextLine();
    array[i] = new String[elements];

    for (int j = 0; j < elements; j++) {
        System.out.print("Enter string: ");
        String word = input.nextLine();
        array[i][j] = word;
    }
}

int[] indices = new int[array.length];
while (indices[0] < array[0].length) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < indices.length; ++i) {
        if (i > 0) {
            sb.append(' ');
        }
        sb.append(array[i][indices[i]]);
    }
    System.out.println(sb.toString());
    for (int i = indices.length - 1; i >= 0; --i) {
        if (++indices[i] < array[i].length) {
            break;
        }
        if (i != 0) {
            indices[i] = 0;
        }
    }
}

Answer 3

My idea is the following. Say we have this 2-d array

String[][] strings = {{"blue", "red"},
                      {"1", "2", "3"},
                      {"dog", "cat", "bird", "fish"}};

We can generate permutation inside an array but with some conditions included.

So firstly we find the maximum line length in our table.

int max = 0;
for (int i = 0; i < strings.length; i++) {
    if(max < strings[i].length) {
        max = strings[i].length;
    }
}

Then we just generate the permutations

int[] permutations = new int[strings.length];

void permute(int k) {
    for(int i = 0; i < max; i++) {
        permutations[k] = i;
        if(valid(k)) {
            if(k == strings.length - 1) {
                printSolution();
            } else {
                permute(k + 1);
            }
        }
    }
}

valid function check that number on position i is not higher than then length on the ith line in our table.

boolean valid(int k) {
    for(int i = 0; i < k; i++) {
        if(permutations[i] >= strings[i].length) return false;
    }
    return true;
}

print solution method:

void printSolution() {
    for(int i = 0; i < strings.length; i++) {
        System.out.print(strings[i][permutations[i]] + " ");
    }
    System.out.println();
}

and the result:

blue 1 dog 
blue 1 cat 
blue 1 bird 
blue 1 fish 
blue 2 dog 
blue 2 cat 
blue 2 bird  
blue 2 fish 
blue 3 dog 
blue 3 cat 
blue 3 bird 
blue 3 fish 
red 1 dog 
red 1 cat 
red 1 bird 
red 1 fish 
red 2 dog 
red 2 cat 
red 2 bird 
red 2 fish 
red 3 dog 
red 3 cat 
red 3 bird 
red 3 fish 

Answer 4

You can use Stream.reduce method.

Try it online!

// original array
String[][] array = {
        {"blue", "red"},
        {"1", "2", "3"},
        {"dog", "cat", "fish", "bird"}};

// array of combinations
String[] combinations = Arrays.stream(array)
        // pairs of a 1D arrays into a single array
        .reduce((arr1, arr2) -> Arrays.stream(arr1)
                // concatenate pairs of strings from two arrays
                .flatMap(str1 -> Arrays.stream(arr2)
                        .map(str2 -> str1 + " " + str2))
                .toArray(String[]::new))
        .orElse(new String[0]);

// column-wise output
int rows = 4;
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < combinations.length; j++) {
        if (j % rows == i)
            System.out.print(
                    (combinations[j] + ";   ").substring(0, 13));
    }
    System.out.println();
}

Column-wise output:

blue 1 dog;  blue 2 dog;  blue 3 dog;  red 1 dog;   red 2 dog;   red 3 dog;   
blue 1 cat;  blue 2 cat;  blue 3 cat;  red 1 cat;   red 2 cat;   red 3 cat;   
blue 1 fish; blue 2 fish; blue 3 fish; red 1 fish;  red 2 fish;  red 3 fish;  
blue 1 bird; blue 2 bird; blue 3 bird; red 1 bird;  red 2 bird;  red 3 bird;  

---

^{See also: How do I generate combinations of two arrays?}