使用Java 8的K个元素的枚举组合 [英] Enumeration Combinations of K elements using Java 8

问题描述

使用Java 8功能给出 List< E> 的实例，如何构建 List< List< E> ; 枚举原始列表的k个元素的所有可能组合？

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?

推荐答案

这是一种算法，我写这篇文章是为了解决一些Euler Project问题：

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

这需要 List< E> 和一个大小，并返回大小为 size 的列表的所有组合，作为 Stream< List< E>> 。

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

这是一种递归算法：其想法是计算大小 size-1 size-1 的所有组合，第一个和第二个除外，当所有元素都包含时，添加第二个元素返回。这一直持续到您达到 size = 0 ，在这里您只返回空组合。请注意，此方法的确会返回重复项（如果返回组合（a，b，c），则（b，c，a）不会返回。）

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.

这篇关于使用Java 8的K个元素的枚举组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！