问题描述
是否有任何最佳方法来获取 n 集的所有并集?
Is there any optimal way to get all union of n sets?
这是我做过的,但是对于大量的集合来说很慢:
This is what I have done, but it is very slow for a large number of sets:
public static void main(String[] args) { List<List<Set<Integer>>> unionSet = new ArrayList<>(); List<List<Integer>> sets = ... double avail = 0; for (int i = 1; i <= sets.size(); i++) { List<Set<Integer>> us = new ArrayList<>(); union(sets, us, new HashSet<>(), i, 0); unionSet.add(us); } }
public static void union( List<List<Integer>> sets, List<Set<Integer>> unionSet, Set<Integer> set, int size, int index) { for (int i = index; i < sets.size(); i++) { Set temp = new HashSet(set); temp.addAll(sets.get(i)); if (size != 1) union(sets, unionSet, temp, size - 1, i + 1); else unionSet.add(temp); } }
n的所有组合的交集 套
推荐答案
你可以使用Stream#flatMap方法如下:
You can use Stream#flatMap method as follows:
如果你有一个sets的list,你可以flatten它的元素(即sets) 到一个 set 的唯一值中:
If you have a list of sets, you can flatten its elements (i.e. sets) into one set of unique values:
List<Set<Integer>> setList = List.of(Set.of(1, 2, 3), Set.of(2, 3, 7)); Set<Integer> set = setList.stream() .flatMap(Set::stream) .collect(Collectors.toSet()); System.out.println(set); // [1, 2, 3, 7]
如果你有一个 deeper 级别的嵌套,那么你必须执行一个 deeper flattening:
If you have a deeper level of nesting, then you have to perform a deeper flattening:
List<List<Set<Integer>>> lists = List.of( List.of(Set.of(1, 2, 3), Set.of(2, 3, 4)), List.of(Set.of(3, 4, 5), Set.of(5, 1, 2))); Set<Integer> set = lists // Stream<List<Set<Integer>>> .stream() // Stream<Set<Integer>> .flatMap(List::stream) // Stream<Integer> .flatMap(Set::stream) .collect(Collectors.toSet()); System.out.println(set); // [1, 2, 3, 4, 5]
如果您有 几个集合,其中 unknown 级别的嵌套,您可以创建一个通用递归展平 方法:
If you have several collections with unknown level of nesting, you can create a generic recursive flattening method:
public static void main(String[] args) { List<Set<Integer>> setList = List.of(Set.of(1, 2, 3), Set.of(2, 3, 7)); List<List<Set<Integer>>> lists = List.of( List.of(Set.of(1, 2, 3), Set.of(2, 3, 4)), List.of(Set.of(3, 4, 5), Set.of(5, 1, 2))); Set<Integer> set = (Set<Integer>) toSet(setList, lists); System.out.println(set); // [1, 2, 3, 4, 5, 7] }
public static Set<?> toSet(Collection<?>... collections) { return Arrays.stream(collections) .flatMap(col -> flattenStream(col.stream())) .collect(Collectors.toSet()); }
public static Stream<?> flattenStream(Stream<?> stream) { return stream.flatMap(e -> { if (e instanceof Collection) { return flattenStream(((Collection<?>) e).stream()); } else { return Stream.of(e); } }); }
另见:
? 并行矩阵乘法
? n 集的所有组合的交集