Java: get all concatenations of List>

Question

I have a List<List<String>> I need to get a List of all possible concatenation on the first dimension

[ [1,2 ], [1] , [3,4] ]

should give:

[ 113, 114, 213, 214 ]

I'm trying with 2 loops, like it should be possible to.

This is what I have tried:

private static List<String> constructIndexes(List<List<String>> indexList){
    List<String> index = new ArrayList<String>();

    String v="";

    for (int i=0; i< indexList.size(); i++){
        List<String> l =  indexList.get(i);
        for (int j=0; j<l.size(); j++){
            if (index.size()>0){
                for (int k=0; k<index.size(); k++){
                    index.set(k, index.get(k)+l.get(j));
                    // System.out.println(">");
                }
            } else {
                index.add(l.get(j));
            }

        }
    }

    return index;
}

some init code:

List<List<String>> indexList = new ArrayList<List<String>>();

    List<String> l = new ArrayList<String>();
    l.add("1");
    l.add("2");
    indexList.add(l);
    l = new ArrayList<String>();
    l.add("1");
    indexList.add(l);
    l = new ArrayList<String>();
    l.add("3");
    l.add("4");
    indexList.add(l);

    System.out.println( constructIndexes(indexList));

So... the concatenation can only go one way? (left-right and not right-left?) — Sephallia, Jun 19 '12 at 22:07
You say that, what doesn't work in your code? What do you get that you don't want? (An error, unexpected output?) — Gareth Latty, Jun 19 '12 at 22:10
@Lattyware I do agree that ciril should put that information in too, but the code is really simple and it's quite easy to see where the problem lies. In his code, the array elements are being added to the index list rather than being concatenated into a string and then being added to the index list. — Sephallia, Jun 19 '12 at 22:14

Adam · Answer 1 · 2012-06-20T06:31:24.013

How about keeping some index counters which track the index of each element, then do traditional carrying to the left, the same you would do if adding, e.g. 9 + 1 = 10 (carry 1 to left, and set 0).

private static List<String> constructIndexes(List<List<String>> indexList) {
    List<String> index = new ArrayList<String>();
    int n = indexList.size();
    int[] counter = new int[n];
    int[] max = new int[n];
    int combinations = 1;
    for (int i = 0; i < n; i++) {
        max[i] = indexList.get(i).size();
        combinations *= max[i];
    }
    int nMinus1 = n - 1;
    for (int j = combinations; j > 0; j--) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            builder.append(indexList.get(i).get(counter[i]));
        }
        index.add(builder.toString());

        counter[nMinus1]++;
        for (int i = nMinus1; i >= 0; i--) {
            // overflow check
            if (counter[i] == max[i]) {
                if (i > 0) {
                    // carry to the left
                    counter[i] = 0;
                    counter[i - 1]++;
                }
            }
        }
    }
    return index;

Test

List<List<String>> test = Arrays.asList(Arrays.asList("1", "2"),
        Arrays.asList("1"), Arrays.asList("3", "4"));
System.out.println(constructIndexes(test));

Output

[113, 114, 213, 214]

thx when possible I will run the 2 answers here on big sets, to check which one can be faster, I would say the recursive one, yours use many checks — , Jun 20 '12 at 05:07
@ciril I would have said mine would be quicker, as method calls usually more expensive than checks in a loop. However after some testing with the input [1], [1,2], up to [1 .. 9] it appears there is virtually no different with both implementations taking around 500ms to complete the work. — Adam, Jun 20 '12 at 06:30
ok (just need to compute the same or differents input 100 times maybe) — , Jun 20 '12 at 07:27

score 0 · Accepted Answer · answered Jun 19 '12 at 22:21

Since the number of lists in the outer list (i.e. the list of lists) is not known until the runtime, you cannot know the number of the loops upfront. In situations like this, you need a recursive solution:

public static void combine(List<List<String>> data, int[] pos, int n, List<String> res) {
    if (n == pos.length) {
        StringBuilder b = new StringBuilder();
        for (int i = 0 ; i != pos.length ; i++) {
            b.append(data.get(i).get(pos[i]));
        }
        res.add(b.toString());
    } else {
        for (pos[n] = 0 ; pos[n] != data.get(n).size() ; pos[n]++) {
            combine(data, pos, n+1, res);
        }
    }
}

Here is how to call it:

List<List<String>> indexList = new ArrayList<List<String>>();
List<String> a = new ArrayList<String>();
a.add("1");
a.add("2");
List<String> b = new ArrayList<String>();
b.add("1");
List<String> c = new ArrayList<String>();
c.add("3");
c.add("4");
indexList.add(a);
indexList.add(b);
indexList.add(c);
List<String> res = new ArrayList<String>();
combine(indexList, new int[indexList.size()], 0, res);
for (String s : res) {
    System.out.println(s);
}

nice thx, yes I was wondering about the complexity, it's product of subList sizes, so yes it's (number of sublist) loops that would have been necessary — , Jun 19 '12 at 22:29

score 0 · Answer 3 · answered Jun 20 '12 at 07:08

Would this work for you

 private <T> List<T> getNthCombination(List<List<T>> lists, int n) {

    List<T> nthCombination = new ArrayList<T>(lists.size());

    int nCarry = n;
    for (List<? extends T> list: lists) {
         int lSize = list.size();
         nthCombination.add(list.get(nCarry % lSize));
         nCarry /= lSize;
    }

    return nthCombination;
}

Of course this is a basic combinatorics problem and there are libraries that handle this kind of stuff.

Java: get all concatenations of List>

3 Answers3

Linked