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

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>和一个大小,并返回大小列表的所有组合size,作为a 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;
}

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