#StackBounty: #java #algorithm #math #combinations #combinatorics Generating All Combinations of List n Levels Deep in Java

Bounty: 50

I’m using the following code to generate a list of combinations of size s:

public static <T extends Comparable<? super T>> List<List<T>> combinations(List<T> items, int size) {
        if (size == 1) {
            List<List<T>> result = new ArrayList<>();
            for (T item : items) {
                result.add(Collections.singletonList(item));
            }
            return result ;
        }
        List<List<T>> result = new ArrayList<>();
        for (int i=0; i <= items.size() - size; i++) {
            T firstItem = items.get(i);
            List<List<T>> additionalItems = combinations(items.subList(i+1, items.size()), size-1) ;
            for (List<T> additional : additionalItems) {
                List<T> combination = new ArrayList<>();
                combination.add(firstItem);
                combination.addAll(additional);
                result.add(combination);
            }
        }
        return result ;
}

Given a list with the values 1, 2 and 3 with a size of 2:

List<Integer> items = new ArrayList<Integer>();
items.add(1);
items.add(2);
items.add(3);

combinations(items, 2)

This produces the following combinations:

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

I’m trying to take this output and generate a 3rd list where each row from the previous output is now combined with every other row – only this time order sensitive and up to ‘d’ levels deep. I’m expecting results similar to the following output:

1 level deep:

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

2 levels deep:

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

3 levels deep:

[1, 2], [1, 3], [1, 2]
[1, 2], [1, 2], [1, 3]
[1, 3], [1, 2], [1, 2]
...

4 levels deep:

 [1, 2], [1, 2], [1, 3], [1, 2]
 [1, 2], [1, 2], [1, 2], [1, 3]
 [1, 2], [1, 3], [1, 2], [1, 2]
 [1, 3], [1, 2], [1, 2], [1, 2]
 [1, 3], [1, 3], [1, 2], [1, 2]
 ...

Note how at 2 levels deep we don’t generate the combination [1, 2], [1, 2] since there is no set of different numbers in between, before or after that set. However, at 3 levels deep we generate the combination [1, 2], [1, 3], [1, 2] since the combination [1, 3] is between the two pairs of [1, 2].

Similarly, at 4 levels deep, we generate the sequence [1, 2], [1, 3], [1, 2], [1, 2] which is not equivalent to the sequence [1, 2], [1, 3], [1, 2] since there’s additional sequence of [1, 2] after [1, 2], [1, 3], [1, 2]. We do not generate the sequence [1, 2], [1, 2], [1, 2], [1, 2] at 4 levels deep since this combination is essentially equivalent to [1, 2] bec there is no new set of numbers in-between, before or after the combination [1, 2].

In short, how do I combine a list of lists of numbers – up to any number of levels deep (1-4 was just used as an example) but this time the result being order sensitive (so
[1, 2], [1, 3] is not equivalent to [1, 3], [1, 2])? The result would likely be stored in a List<List<List<Integer>>>.

I’ve searched around on StackOverflow and have seen several threads on generating combinations (such as this one and this one) but did not address the exact situation outlined above.

Thanks


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.