Generating All Combinations of List n Levels Deep in Java

Question

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 of the three rows from 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, 2], [1, 3]]
[[1, 2], [1, 2], [2, 3]]
[[1, 2], [1, 3], [1, 2]]
[[1, 2], [1, 3], [1, 3]]
[[1, 2], [1, 3], [2, 3]]
[[1, 2], [2, 3], [1, 2]]
[[1, 2], [2, 3], [1, 3]]
[[1, 2], [2, 3], [2, 3]]
[[1, 3], [1, 2], [1, 2]]
[[1, 3], [1, 2], [1, 3]]
[[1, 3], [1, 2], [2, 3]]
[[1, 3], [1, 3], [1, 2]]
[[1, 3], [1, 3], [2, 3]]
[[1, 3], [2, 3], [1, 2]]
[[1, 3], [2, 3], [1, 3]]
[[1, 3], [2, 3], [2, 3]]
[[2, 3], [1, 2], [1, 2]]
[[2, 3], [1, 2], [1, 3]]
[[2, 3], [1, 2], [2, 3]]
[[2, 3], [1, 3], [1, 2]]
[[2, 3], [1, 3], [1, 3]]
[[2, 3], [1, 3], [2, 3]]
[[2, 3], [2, 3], [1, 2]]
[[2, 3], [2, 3], [1, 3]]

4 levels deep:

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

Note how at 2 levels deep the combination [1, 2], [1, 2] is not generated since there's 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 present 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

Middleweight

"each row from the previous output is now combined with every other row" seems unclear. What exactly is "every other row"? (Providing complete, rather than redacted, output might help with this but ideally the desired method will be more carefully defined.) – Shrill

I believe you're looking for Apriori algorithm. en.wikipedia.org/wiki/Apriori_algorithm – Eleneeleni

@גלעדברקן Updated question with clarification & complete output. – Middleweight

Answer 1

I believe I made what you are looking for. The code is split up into four separate methods(You didn't make any distinction if it had to be only 1):

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int level) {
    List<List<List<T>>> result = new ArrayList<>();
    if(level == 1) {
        for(List<T> item : items) {
            result.add(Collections.singletonList(item));
        }
        return result;
    }

    for(int i = 0; i < level; i++) {
        if(i == 0) {
            for(List<T> item : items)
                result.add(Collections.singletonList(item));
            continue;
        }

        List<List<List<T>>> newResult = new ArrayList<>();
        for(List<List<T>> item : result) {
            List<List<List<T>>> combined = new ArrayList<>();
            List<T> first = item.get(0);
            for(int j = 0; j < items.size(); j++) {
                List<List<T>> current = new ArrayList<>();
                List<T> it = items.get(j);
                current.addAll(item);
                current.add(it);

                combined.add(current);
            }

            newResult.addAll(combined);
        }

        result = newResult;
    }

    clean(result);
    return result;
}

This is what does the majority of the algorithm. First, like in the function you provided, it checks to see if the level is 1, in which case you can just return a list of list, like in the given method. After that, we loop over however many levels we have. We first check to see if the current level is 1, in which case it will just do the same thing as if the method were called with a level of 1. Next we create a new list called newResult. This variable is basically a temporary value of result to prevent a concurrent modification exception. Then we loop through every value already in result. We create a few new values based on whatever value we have, and add them to combined. We then add combined into newResult, and the algorithm is basically over. Now, those loops don't count for when all of the values are the same, for example, [1, 2], [1, 2], [1, 2], [1, 2]. So we call the clean method to remove those cases.

public static <T extends Comparable<? super T>> void clean(List<List<List<T>>> list) {
    List<List<List<T>>> removals = new ArrayList<>();
    for(List<List<T>> item : list) {
        if(!check(item))
            removals.add(item);
    }
    for(List<List<T>> item : removals) {
        list.remove(item);
    }
}

This method runs through everything inside of the given list, and runs the check method on the element. That method is explained further down. If the element is not valid, it is marked for removal, and is removed in the next loop.

public static <T extends Comparable<? super T>> boolean check(List<List<T>> list) {
    if(list.size() < 2) return true;

    for(int i = 1; i < list.size(); i++) {
        List<T> previous = list.get(i-1);
        List<T> item = list.get(i);

        if(notEqual(previous, item)){
            return true;
        }
    }

    return false;
}

This loop checks to see if a given list is valid, by comparing one list against another, until it finds two that aren't the same. When that happens, the list is valid, and returns true. If not, it will never return, will break out of the loop, and return false.

public static <T extends Comparable<? super T>> boolean notEqual(List<T> a, List<T> b) {
    for(int i = 0; i < Math.min(a.size(), b.size()); i++) {
        T ao = a.get(i);
        T bo = b.get(i);

        if(ao.compareTo(bo) != 0)
            return true;
    }

    return false;
}

This method takes two input lists, and checks to see if the elements inside of them aren't equal. It loops over both lists, getting the elements at the same index, and compares them to one another. If they are not equal, it returns true, and otherwise, it finishes the loop and returns false.

Please note that this is simply a proof of concept and not a finished version. A lot of aspects of it could definitely be improved upon, but this is a working version of what you asked for.

Link to working version on jDoodle

If you have any questions about any aspect of it, or want anything clarified, don't hesitate to ask!

Edit: I have revised the algorithm to incorporate what you have asked for. Here is the new code:

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int minLevel, int maxLevel) {
    List<List<List<T>>> result = new ArrayList<>();

    for(int i = minLevel; i < maxLevel+1; i++) {
        result.addAll(level(items, i));
    }

    return result;
}

This is the overloaded method that will allow you to specify the range of levels you want. Given a minimum and maximum level, it will return a new list containing all of the levels within that range, inclusive. As you said, it is relatively trivial, as a simple loop.

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int level) {
    List<List<List<T>>> result = new ArrayList<>();
    if(level == 1) {
        for(List<T> item : items) {
            result.add(Collections.singletonList(item));
        }
        return result;
    }

    for(int i = 0; i < level; i++) {
        if(i == 0) {
            for(List<T> item : items)
                result.add(Collections.singletonList(item));
            continue;
        }

        List<List<List<T>>> newResult = new ArrayList<>();
        for(List<List<T>> item : result) {
            if(item.size() < i)
                continue;

            List<List<List<T>>> combined = new ArrayList<>();
            List<T> first = item.get(0);
            for(int j = 0; j < items.size(); j++) {
                List<List<T>> current = new ArrayList<>();
                List<T> it = items.get(j);
                current.addAll(item);
                current.add(it);

                combined.add(current);
            }

            newResult.addAll(combined);
        }

        result = newResult;
    }

    List<List<List<T>>> removals = new ArrayList<>();
    for(List<List<T>> item : result) {
        if(!check(item))
            removals.add(item);
    }
    for(List<List<T>> item : removals) {
        result.remove(item);
    }

    return result;
}

Here is the revised method. I removed the clean method, and just put it inside of the level method, as it was only called once. I don't think it is really possible, at least with the current code to run that clean method during the algorithm, because at this point in time, the way it works is it generates all possible combinations for a given level, then goes to the next one. If combinations that are the same were removed, on the next level, those combinations wouldn't be added.

Here is an example: Say I have [1, 2], [1, 3], [2, 3]. If I went to level two, I would have the combinations specified in your question. Pretty obvious right? Well, if I then went on to level 3, only using the results from level 2, I would miss out on all combinations containing [1, 2], [1, 2] [...], since that is not in the given list. This is an issue with the algorithm, and could definitely be improved upon.

I plan on further refactoring this, to make it check inside the algorithm, but it might take me a hot minute to do that.

New working version in jDoodle

Edit 2: Incorporating the clean method inside of the algorithm was actually much simpler than I initially thought. Here is the new code with a couple of comments:

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int level) {
    List<List<List<T>>> result = new ArrayList<>();
    for(int i = 0; i < level; i++) {
        if(i == 0) { // If level is 0, we can just add the items as singleton lists to the result
            for(List<T> item : items)
                result.add(Collections.singletonList(item));
            continue;
        }

        List<List<List<T>>> newResult = new ArrayList<>(); // Temporary items that will be added
        for(List<List<T>> item : result) {
            if(item.size() < i) // Make sure we are manipulating items that are on the previous level
                continue;

            List<List<List<T>>> combined = new ArrayList<>(); // The temporary values for this specific item
            for(int j = 0; j < items.size(); j++) {
                List<List<T>> current = new ArrayList<>(); // The current list with the value
                current.addAll(item); // Add the current items from result to the list
                current.add(items.get(j)); // Add the current item from items to the list

                if (i == level-1 && !check(current)) { // If this is the last level, and the current list shouldn't be added, skip adding
                    continue;
                }

                combined.add(current); // Add the current list to the combined values
            }

            newResult.addAll(combined); // Add all of the lists in combined to the new result
        }

        result = newResult; // Make result equal to the new result
    }

    return result;
}

Now what it does is, when adding a new combination to the list, it first checks if the current level is the final one. If so, it actually checks the list, and if it is not valid, it skips actually adding it.

I again plan on completely rewriting the algorithm in a much more intelligent format, but this code completely works right now.

Working version on jDoodle

Spoonful

I believe this is the correct answer and thanks for the explanation after each section of code. Two quick questions: 1) Is it possible to incorporate the clean() method in the algorithm itself, instead of removing dups in a separate function? 2) Final list List<List<List<T>>> should contain all levels within specified range. If minLevel = 1 and maxLevel = 4 then it would contain levels 1-4. I believe this is relatively trivial to implement by creating a new method called 'levels' with parameters minLevel and maxLevel & fusing all lists in List<List<List<T>>>. – Middleweight

Try editing the code tlll you get it working, @Alan Cook – Carilyn

@AlanCook I have implemented everything you requested, but I am still going to completely rewrite it, to be more intelligent when filling the list. – Spoonful