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

Question

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

Answer 1

这是我为解决一些欧拉计划问题而编写的算法:

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>和尺寸并返回尺寸列表的所有组合 size , 作为 Stream<List<E>> .

这是一个递归算法:其思想是计算大小的组合 size - 1在列表的所有元素上，除了第一个。当你拥有所有这些时，你只需在每个组合的开头添加你删除的第一个元素。然后，您继续寻找大小 size - 1 的所有组合在列表的所有元素上，除了第一个和第二个，当你拥有所有元素时，你将第二个元素添加回来。这一直持续到您到达 size = 0 ，您只需返回空组合。请注意，此方法确实会返回“重复项”(如果返回组合 (a, b, c)，则不会返回 (b, c, a))。

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

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

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