Value combinations of n subarrays in Java

Question

I want to create a Java method, which accepts an inputArray = Object[n][], where n can be any integer, and outputs a list of possible n-size combinations between all values of the n subarrays. Below is an example:

Input Array: (where Object=String and n=3)

String[] subarrayA = {"A0","A1","A2"};
String[] subarrayB = {"B0","B1"};
String[] subarrayC = {"C0","C1","C2","C3"};
String[3][] inputArray = {subarrayA, subarrayB, subarrayC};

Desired Output:

{A0,B0,C0},{A0,B0,C1},{A0,B0,C2},{A0,B0,C3},
{A0,B1,C0},{A0,B1,C1},{A0,B1,C2},{A0,B1,C3},
{A1,B0,C0},{A1,B0,C1},{A0,B0,C2},{A1,B0,C3},
{A1,B1,C0},{A1,B1,C1},{A1,B1,C2},{A1,B1,C3},
{A2,B0,C0},{A2,B0,C1},{A2,B0,C2},{A2,B0,C3},
{A2,B1,C0},{A2,B1,C1},{A2,B1,C2},{A2,B1,C3}

Obviously, I cannot have a fixed nested-loop inside my method since I do not know n in advance. So, I am guessing the only way to solve it would be through a recursive method? Any recommendations?

P.S: I am aware of the simple combination-related posts on the website.

No, this is not a homework. I am trying to create a prior probability table for my Bayesian network, based on a dataset that only has 'categorical' columns. I need the combinations to create SQL queries with the given column values on the fly. — Zhubarb, Feb 25 '12 at 19:02
In proper mathematical terms, the desired output is the *cartesian product* of the n input sets. ("n-size combinations between all values of the n subarrays" would probably include {A0,A1,B0}, too.) — meriton, Feb 25 '12 at 19:03

score 6 · Accepted Answer · edited Feb 27 '12 at 01:36

6

This should solve your problem.

public static void permute(String array[][], int index, ArrayList<String> output){

    if(index == array.length){
        System.out.println(output.toString());
    }
    else{
        for(int i=0 ; i<array[index].length ; i++){
            output.add(array[index][i]);
            permute(array,index+1,output);
            output.remove(output.size() - 1); 
        }
    }
}

edited Feb 27 '12 at 01:36

Zhubarb

11,432
18
75
114

answered Feb 25 '12 at 18:59

JProgrammer

1,135
1
10
27

Thank you very much fro your help. I am not a programmer by training and find recursion quite unintuitive, i.e. hard. – Zhubarb Feb 26 '12 at 22:36
is this complexity dependent on the r in nCr? – LZH Oct 29 '14 at 00:31
@JProgrammer Can you explain how this works. I don't understand how `output.remove(output.size() - 1);` is ever executed if it is after you call `permute(array,index+1,output);`. Wouldn't calling `permute()` cause `output.remove()` to never be called? – enrique2334 Dec 04 '14 at 02:33
This is difficult to explain in words. 'if(index == array.length)' will prevent calling permute eventually. I am pretty sure that there are animation to demonstrate how this exactly works. – JProgrammer Jul 15 '15 at 00:08
Every function call will return to the point it is called and continue executing after, even successive recursive calls. Use a stack and trace the calls out on paper. Notice what happens when if(index == array.length) is true. The sequence is printed. When it returns at that point it continues after the recursive call removing the last string and continuing the for loop to output the next permutation. – Aaron Dancygier Jul 03 '16 at 09:25

Value combinations of n subarrays in Java

1 Answers1