当两个元素相同时，合并设置 [英] Merge sets when two elements in common
问题描述
这是比较集
的跟进b$ b
我有
Set< Set< Node>> NestedSet = new HashSet< Set< Node>>（）;
$ b $ [Node [0]，Node [1]，Node [2]]，[Node [0]，Node [2]，Node [6]]，[Node [3]，Node [4]，Node [5]] [Node [2]，Node [6]，Node [7]]]
如果有两个共同的元素，我想合并这些集合。例如0,1,2和0,2,6有两个共同的元素，所以它们合并形成[0,1,2,6]。
再次[0,1,2,6]和[2,6,7]有2和6共同点。所以合并它们并得到[0,1,2,6,7]。
最终的输出应该是：
$ b $ pre $ [[Node [0 ]，Node [1]，Node [2]，Node [6]，Node [7]]，[Node [3]，Node [4]，Node [5]]]
我尝试过这样：
for Set< Node> s1：NestedSet）{
可选< Set< Node>> findFirst = result.stream（）。filter（p - > {HashSet< Node> temp = new HashSet<>（s1）;
temp.retainAll（p）;
return temp.size ）== 2;}）。findFirst（）;
if（findFirst.isPresent（））{
findFirst.get（）。addAll（s1）;
}
else {
result.add（s1）;
}
}
但是我得到的结果是：
$ b $ $ p $
[[Node [0]，Node [1]，Node [2]，Node [6]，Node [7] ]，[Node [3]，Node [4]，Node [5]]，[Node [0]，Node [2]，Node [6]，Node [7]]]
任何想法？有什么办法可以得到想要的输出吗？
一些注意事项：
- 每次应用合并时，都必须重新启动该过程并遍历修改后的集合。因此，输入集的迭代次序很重要，如果你希望你的代码是确定性的，你可能想要使用集合来保证它们的迭代次序（例如使用
LinkedHashSet（不是HashSet）或List。 - 因为它会在合并时修改提供的集合，一般来说，我认为它会尽可能避免创建副作用。 以下代码可以实现您想要的功能：
pre $ static $ T> List< < T>> unmergedSets）{
final List< Set< T>> mergedSets = new ArrayList<>（unmergedSets）;
List< Integer> mergeCandidate = Collections.emptyList （）;
do {
mergeCandidate = findMergeCandidate（mergedSets）;
//应用合并
if（！mergeCandidate.isEmpty（））{
//收集集合合并
final Set< T> mergedSetSet = Sets.union（
mergedSets.get（mergeCandidate.get（0）），
mergedSets.get（mergeCandidate.get（1）））;
//使用它们的索引删除两个集合，以最高索引
开始mergedSets.remove（mergeCandidate.get（0）.intValue（））;
mergedSets.remove（mergeCandidate.get（1）.intValue（））;
//添加mergedSet
mergedSets.add（mergedSet）;
}
} while（！mergeCandidate.isEmpty（））;
返回mergedSets;
}
// O（n ^ 2/2）
static< T>列表与LT;整数> findMergeCandidate（List< Set< T> sets）{
for（int i = 0; i< sets.size（）; i ++）{
for（int j = i + 1; j < sets.size（）; j ++）{
if（Sets.intersection（sets.get（i），sets.get（j））。size（）== 2）{
return Arrays .asList（j，i）;
}
}
}
返回Collections.emptyList（）;
}
为了测试这个方法，我创建了两个辅助方法：
static Set< Integer> set（int ... ints）{
返回新的LinkedHashSet<>（Ints.asList（ints））;
}
@SafeVarargs
static< T>设置<设置< T>> set（Set< T> ... sets）{
return new LinkedHashSet<>（Arrays.asList（sets））;
}
这些辅助方法允许编写非常易读的测试，例如（使用数字从这个问题）：
pre $ public static void main（String [] args）{
// prints [[2 ，6,7,0,1]]
System.out.println（mergeSets（sets（set（0，1，2，6），set（2，6，7））））;
//打印[[3,4,5]，[0,2,6,1,7]]
System.out.println（
mergeSets（sets（set（0， 1，2），设置（0,2,6），设置（3,4,5），设置（2,6,7））））;
}
This is the follow up of compare sets
I have
Set<Set<Node>> NestedSet = new HashSet<Set<Node>>();
[[Node[0], Node[1], Node[2]], [Node[0], Node[2], Node[6]], [Node[3], Node[4], Node[5]] [Node[2], Node[6], Node[7]] ]
I want to merge the sets when there are two elements in common. For example 0,1,2 and 0,2,6 has two elements in common so merging them to form [0,1,2,6].
Again [0,1,2,6] and [2,6,7] has 2 and 6 common. so merging them and getting [0,1,2,6,7].
The final output should be :
[ [Node[0], Node[1], Node[2], Node[6], Node[7]], [Node[3], Node[4], Node[5]] ]
I tried like this :
for (Set<Node> s1 : NestedSet ) {
Optional<Set<Node>> findFirst = result.stream().filter(p -> { HashSet<Node> temp = new HashSet<>(s1);
temp.retainAll(p);
return temp.size() == 2; }).findFirst();
if (findFirst.isPresent()){
findFirst.get().addAll(s1);
}
else {
result.add(s1);
}
}
But the result I got was :
[[Node[0], Node[1], Node[2], Node[6], Node[7]], [Node[3], Node[4], Node[5]], [Node[0], Node[2], Node[6], Node[7]]]
Any idea ? Is there any way to get the desired output?
Some considerations:
- Each time you apply a merge, you have to restart the procedure and iterate over the modified collection. Because of this, the iteration order of the input set is important, if you want your code to be deterministic you may want to use collections that give guarantees over their iteration order (e.g. use
LinkedHashSet(notHashSet) orList. - Your current code has side effects as it modifies the supplied sets when merging. In general I think it helps to abstain from creating side effects whenever possible.
The following code does what you want:
static <T> List<Set<T>> mergeSets(Collection<? extends Set<T>> unmergedSets) {
final List<Set<T>> mergedSets = new ArrayList<>(unmergedSets);
List<Integer> mergeCandidate = Collections.emptyList();
do {
mergeCandidate = findMergeCandidate(mergedSets);
// apply the merge
if (!mergeCandidate.isEmpty()) {
// gather the sets to merge
final Set<T> mergedSet = Sets.union(
mergedSets.get(mergeCandidate.get(0)),
mergedSets.get(mergeCandidate.get(1)));
// removes both sets using their index, starts with the highest index
mergedSets.remove(mergeCandidate.get(0).intValue());
mergedSets.remove(mergeCandidate.get(1).intValue());
// add the mergedSet
mergedSets.add(mergedSet);
}
} while (!mergeCandidate.isEmpty());
return mergedSets;
}
// O(n^2/2)
static <T> List<Integer> findMergeCandidate(List<Set<T>> sets) {
for (int i = 0; i < sets.size(); i++) {
for (int j = i + 1; j < sets.size(); j++) {
if (Sets.intersection(sets.get(i), sets.get(j)).size() == 2) {
return Arrays.asList(j, i);
}
}
}
return Collections.emptyList();
}
For testing this method I created two helper methods:
static Set<Integer> set(int... ints) {
return new LinkedHashSet<>(Ints.asList(ints));
}
@SafeVarargs
static <T> Set<Set<T>> sets(Set<T>... sets) {
return new LinkedHashSet<>(Arrays.asList(sets));
}
These helper methods allow to write very readable tests, for example (using the numbers from the question):
public static void main(String[] args) {
// prints [[2, 6, 7, 0, 1]]
System.out.println(mergeSets(sets(set(0, 1, 2, 6), set(2, 6, 7))));
// prints [[3, 4, 5], [0, 2, 6, 1, 7]]
System.out.println(
mergeSets(sets(set(0, 1, 2), set(0, 2, 6), set(3, 4, 5), set(2, 6, 7))));
}
这篇关于当两个元素相同时，合并设置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
