Enumeration Combinations of K elements using Java 8

Question

Given an instance of List<E>, using Java 8 features, how is it possible to build a List<List<E>> enumerating all possible combinations of k elements of the original List?

Answer 1

This is an algorithm that I wrote for solving some Euler Project problems :

public static <E> Stream<List<E>> combinations(List<E> l, int size) {
    if (size == 0) {
        return Stream.of(Collections.emptyList()); 
    } else {
        return IntStream.range(0, l.size()).boxed().
            <List<E>> flatMap(i -> combinations(l.subList(i+1, l.size()), size - 1).map(t -> pipe(l.get(i), t)));
    }
}

private static <E> List<E> pipe(E head, List<E> tail) {
    List<E> newList = new ArrayList<>(tail);
    newList.add(0, head);
    return newList;
}

It takes a List<E> and a size and returns all the combinations of the list of size size, as a Stream<List<E>>.

It is a recursive algorithm : the idea is to calculate the combinations of size size - 1 on all elements of the list except the first. When you have them all, you just add the first element you removed at the beginning of each of the combinations. You then continue by looking for all combinations of size size - 1 on all elements of the list except the first and the second, and when you have them all, you add the second element back. This continues until you reach size = 0, where you just return empty combinations. Beware that this method that does return "duplicates" (if combination (a, b, c) is returned then (b, c, a) is not returned).

You did not mention whether duplicates should be included. Modifying this algorithm to contain duplicates is not difficult, the logic is a bit different.

public static <E> Stream<List<E>> combinationsDupl(List<E> l, int size) {
    if (size == 0) {
        return Stream.of(Collections.emptyList()); 
    } else {
        return l.stream().<List<E>> flatMap(h -> combinationsDupl(subtract(l, h), size - 1).map(t -> pipe(h, t)));
    }
}

private static <E> List<E> pipe(E head, List<E> tail) {
    List<E> newList = new ArrayList<>(tail);
    newList.add(0, head);
    return newList;
}

private static <E> List<E> subtract(List<E> list, E e) {
    List<E> newList = new ArrayList<>(list);
    newList.remove(e);
    return newList;
}

This time, you traverse all the elements in the input list. For each of them, you calculate the combinations of the list where this element is removed. Then, when you have them all, you add it again to each of the combinations.

Answer 2

This solution is not recursive (which makes it a bit clearer) and lazy, however the returned combinations are not ordered by increasing length:

public class Combinations {

    public static void main(String[] args) {
        System.out.println(
                getCombinationsStream(Arrays.asList(1, 2, 3))
                        .collect(Collectors.toList()));
        // prints: [[1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
    }

    public static <T> Stream<List<T>> getCombinationsStream(List<T> list) {
        // there are 2 ^ list.size() possible combinations
        // stream through them and map the number of the combination to the combination
        return LongStream.range(1 , 1 << list.size())
                .mapToObj(l -> bitMapToList(l, list));
    }

    public static <T> List<T> bitMapToList(long bitmap, List<T> list) {
        // use the number of the combination (bitmap) as a bitmap to filter the input list
        return IntStream.range(0, list.size())
                .filter(i -> 0 != ((1 << i) & bitmap))
                .mapToObj(list::get)
                .collect(Collectors.toList());
    }
}

EDIT: to get only combinations of a specific length, add a .filter() in somewhere.