CODEWITHSUNDEEP
javaalgorithm
user1125394
user1125394

Reputation:

Java: get all concatenations of List<List<String>>

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));

Upvotes: 1

Views: 913

Answers (3)

COME FROM
COME FROM

Reputation: 2507

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.

Upvotes: 0

Adam
Adam

Reputation: 36723

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]

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726779

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);
}

Upvotes: 0

Related Questions