我如何采取集合的并集? [英] How do I take the union of sets?
问题描述
是否有最佳方法来获取 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);
}
}
推荐答案
You can use Stream#flatMap
method as follows:
-
如果您有一个列表的 sets ,则可以 flatten 其元素(即 sets )放入一组唯一值的 :
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]
如果您有多个集合具有未知嵌套级别,则可以创建通用递归展平方法:
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
个集合的所有组合的交集
See also:
• Parallelized Matrix Multiplication
• The intersection of all combinations of n
sets
这篇关于我如何采取集合的并集?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!