使用Java的K个元素的枚举组合 8

Question

给定一个 List<E> 的实例，使用 Java 8 个特征，如何构建一个 List<List<E>> 枚举原始 List 的 k 个元素的所有可能组合？

Answer 1

这是我为解决一些 Euler Project 问题而编写的算法：

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

它需要一个 List<E> 和一个大小 returns 大小为 size 的列表的所有组合，作为一个 Stream<List<E>>.

这是一种递归算法：其思想是计算列表中除第一个元素之外的所有元素的大小 size - 1 的组合。当你拥有所有这些时，你只需在每个组合的开头添加你删除的第一个元素。然后继续查找列表中除第一个和第二个元素之外的所有元素的大小 size - 1 的所有组合，当你拥有所有元素时，你将第二个元素添加回去。这一直持续到您到达 size = 0，在那里您只有 return 个空组合。请注意，此方法执行 return "duplicates"（如果组合 (a, b, c) 是 returned，则 (b, c, a) 不是 returned）。

你没有提到是否应该包含重复项。修改此算法以包含重复项并不难，逻辑有点不同。

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

这一次，您遍历输入列表中的所有元素。对于它们中的每一个，您计算删除此元素的列表的组合。然后，当你拥有它们时，你再次将它添加到每个组合中。

Answer 2

这个解决方案不是递归的（这使它更清晰一些）并且是惰性的，但是返回的组合不是按长度递增排序的：

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

编辑：要仅获取特定长度的组合，请在某处添加 .filter()。

使用Java的K个元素的枚举组合 8

Enumeration Combinations of K elements using Java 8

java

combinations

functional-programming

java-8