Combination in java

Question

I have an array that contains 3 arrays, like this:

String[][] S = { {a,b,c} , {d,e}, {f,g,h} }

Now I want to create all arrays

R = {r1,r2,r3}

where r1 belongs to S1, r2 belongs to S2, r3 belongs to S3 (S1, S2, S3 are sub-array of S) and I want have the output like that:

R1 = {S[1][1], S[2][1], S[3][1]},
R2 = {S[1][1], S[2][1], S[3][2]},
R3 = {S[1][1], S[2][1], S[3][3]},
...,
R18 = {S[1][3], S[2][2], S[3][3]}

I can not use 3 for-iterators because the array S is dynamic.

_I can not use 3 for-iterators because the array S is dynamic_ That is what the `.length` property is for. — Keppil, Sep 17 '14 at 15:23
I don't understand completely your problem, but seems like you're more used to other programming languages. In java there are more things to work than arrays (which by the way start at zero). You can use anything in java.util or you could even use google guava library to accumulate, transform, etc. Do you have a reference to the algorithm you want to implement? explanation is a little bit difficult. — Luis Ramirez-Monterosa, Sep 17 '14 at 15:26
Thanks for comment but I think my question is clear. My problem is how to implement an algorithm with that input and output. I can not use 3 for-iterator because it is not generic enough and doesn't scale. — Bidi, Sep 17 '14 at 15:32
Do you mean that S may contain more (or less) than 3 arrays? — alexander zak, Sep 17 '14 at 15:35
What you mean with _the array S is dynamic_? Means you don't know the size of the array when you have to process it? Or that you modify the size at runtime? That sounds as a `List` job... — Narmer, Sep 17 '14 at 15:36
Yes, the length of S is dynamic.The number 3 here is just an example. S is a 2-dimension array. Sorry for poor English :) — Bidi, Sep 17 '14 at 15:38
The fact that the length of `S` is dynamic doesn't mean you cannot use a `for` loop. And why is this cataloged as genetic algorithm as well? — Luiggi Mendoza, Sep 17 '14 at 15:39
If the array is already full when you process it, nothing stops you on using `S.length`. And for each "sub array" `S[x].length`. — Narmer, Sep 17 '14 at 15:41
_Thanks for comment but I think my question is clear._ Understanding your own question is seldom difficult. If someone requests clarifications it is often because they are needed. — Keppil, Sep 17 '14 at 15:43
@Narmer Sorry, I don't know what you mean. Of course I can use S.length but the array is dynamic, I want to process it in any case, 4 or 5 or n sub-arrays. — Bidi, Sep 17 '14 at 15:45
So let me get this straight: `S` is a "vector of vectors", and each `S[j]` can have different length. I don't see any restriction to use `for{}` loops — Barranka, Sep 17 '14 at 15:47
@Bidi Look at the question, it contains a link of previous thread discussing the same thing. Only difference the old thread was using an array of `Set`s instead of 2D arrays, but it is easily to modify the solutions from the linked thread to your case. Good Luck. — amit, Sep 17 '14 at 15:53
@Barranka How can you use for loops? Say you have `k` for loops. The complexity of this problem will be `n^k`. However, if you have `m>>k` arrays, there are `n^m >> n^k` elements you need to generate. This is cartesian product, and cannot be solved easily using loops since the number of elements you need to generate is exponential in the number of sets you have. Since the number of sets is unknown apriori - you cannot pre-determine how many for loops you are going to need. — amit, Sep 17 '14 at 15:55

alexander zak · Answer 1 · 2014-09-17T16:13:27.377

Here is a solution using recursion.

private static void fillArray(List<String> prefix, String[][] s, List<String[]> allResults){
    if(prefix.size() < s.length) {
        String[] currentArray = s[prefix.size()];
        for (String currentString : currentArray) {
            LinkedList<String> copy = new LinkedList<>(prefix);
            copy.add(currentString);
            fillArray(copy,s,allResults);
        }
    } else {
        allResults.add(prefix.toArray(new String[prefix.size()]));
    }
}

To use it call:

    String[][] S = { {"a","b","c"} , {"d","e"}, {"f","g","h"} };
    List<String[]> allResults = new LinkedList<>();
    fillArray(new LinkedList<String>(),S,allResults);

    for (String[] result: allResults) {
        System.out.println(Arrays.toString(result));
    }

EDIT:

Here is a method for what you want:

private static void fillArray2(List<String> prefix, String[][] s, List<String[]> allResults){
    if(prefix.size() < s.length) {
        String[] currentArray = s[prefix.size()];
        for(int i=0;i<currentArray.length;i++) {
            LinkedList<String> copy = new LinkedList<>(prefix);
            copy.add("S["+(prefix.size()+1)+"]["+(i+1)+"]");
            fillArray2(copy,s,allResults);
        }
    } else {
        allResults.add(prefix.toArray(new String[prefix.size()]));
    }
}

Combination in java

1 Answers1