当两个元素相同时合并集合

Question

这是

的跟进

我有

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]] ]

我想在有两个共同元素时合并集合。例如 0,1,2 和 0,2,6 有两个共同的元素，所以将它们合并形成 [0,1,2,6]。

同样 [0,1,2,6] 和 [2,6,7] 有 2 和 6 公共。所以合并它们并得到 [0,1,2,6,7]。

最终输出应该是：

[  [Node[0], Node[1], Node[2], Node[6], Node[7]], [Node[3], Node[4], Node[5]] ]

我这样试过：

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

                    }

但我得到的结果是：

[[Node[0], Node[1], Node[2], Node[6], Node[7]], [Node[3], Node[4], Node[5]], [Node[0], Node[2], Node[6], Node[7]]]

有什么想法吗？有没有办法得到想要的输出？

Answer 1

我不确定你为什么会得到那个结果，但我确实看到了这段代码的另一个问题：它是 order-dependent。例如，即使代码按预期工作，[Node[0], Node[1], Node[2]] 是否首先与 [Node[0], Node[2], Node[6]] 或 [Node[2], Node[6], Node[7]] 进行比较也很重要。但是 Sets 没有定义的顺序，因此结果是 non-deterministic 或 implementation-dependent，具体取决于您如何看待它。

如果您真的想要确定性的 order-dependent 操作，您应该使用 List<Set<Node>>，而不是 Set<Set<Node>>。

Answer 2

一些注意事项：

每次应用合并时，都必须重新启动过程并迭代修改后的集合。因此，输入集的迭代顺序很重要，如果您希望代码具有确定性，您可能希望使用可以保证其迭代顺序的集合（例如使用 LinkedHashSet（而不是 HashSet ) 或 List.
您当前的代码有副作用，因为它在合并时修改了提供的集合。总的来说，我认为尽可能避免产生副作用是有帮助的。

以下代码可以满足您的需求：

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

为了测试这个方法，我创建了两个辅助方法：

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

这些辅助方法允许编写非常可读的测试，例如（使用问题中的数字）：

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

Answer 3

这是使用递归的简洁方法：

public static <T> Set<Set<T>> mergeIntersectingSets(Collection<? extends Set<T>> unmergedSets) {
    boolean edited = false;
    
    Set<Set<T>> mergedSets = new HashSet<>();
    for (Set<T> subset1 : unmergedSets) {
        boolean merged = false;
        
        // if at least one element is contained in another subset, then merge the subsets
        for (Set<T> subset2 : mergedSets) {
            if (!Collections.disjoint(subset1, subset2)) {
                subset2.addAll(subset1);
                merged = true;
                edited = true;
            }
        }
        // otherwise, add the current subset as a new subset
        if (!merged) mergedSets.add(subset1);
    }
    
    if (edited) return mergeIntersectingSets(mergedSets); // continue merging until we reach a fixpoint
    else return mergedSets;
}

当两个元素相同时合并集合

Merge sets when two elements in common

java

lambda

graph

set