如何通过交集来过滤一组集合？

Question

我需要通过集合的交集来联合一组集合，并编写一个具有这种签名的函数。

Collection<Set<Integer>> filter(Collection<Set<Integer>> collection);

这里是集合的简单示例。

1) {1,2,3}
2) {4}
3) {1,5}
4) {4,7}
5) {3,5}

在这个例子中，我们可以看到集合1、3和5相交。我们可以将它重写为一个新的集合{1,2,3,5}。另外，我们还有两个带有交集的集合，它们是2和4，我们可以创建一个新的集合{4,7}。输出结果将是两个集合的集合：{1,2,3,5}和{4,7}。

我不知道从哪里开始解决这个任务。

- Mark

---

当然可以。它应该是两个集合的集合（{1,2,3,5} 和 {4,7}）。 - Mark

@ketrox 给定集合的幂可以是随机的。 - Mark

https://en.wikipedia.org/wiki/Disjoint-set_data_structure - MBo

如果输出的结果包含输入中不存在的元素，那么这并不真正是一个“过滤器”。 - Oliver Charlesworth

@OliverCharlesworth 是的，它类似于 groupBy。 - Mark

Answer 1

这应该可以解决你的用例。可能有更高效的实现方式，但我想这应该能给你一个开始的想法：

private static Collection<Set<Integer>> mergeIntersections(Collection<Set<Integer>> collection) {
    Collection<Set<Integer>> processedCollection = mergeIntersectionsInternal(collection);
    while (!isMergedSuccessfully(processedCollection)) {
        processedCollection = mergeIntersectionsInternal(processedCollection);
    }
    return processedCollection;
}

private static boolean isMergedSuccessfully(Collection<Set<Integer>> processedCollection) {
    if (processedCollection.size() <= 1) {
        return true;
    }
    final Set<Integer> mergedNumbers = new HashSet<>();
    int totalNumbers = 0;
    for (Set<Integer> set : processedCollection) {
        totalNumbers += set.size();
        mergedNumbers.addAll(set);
    }
    if (totalNumbers > mergedNumbers.size()) {
        return false;
    }
    return true;
}

private static Collection<Set<Integer>> mergeIntersectionsInternal(Collection<Set<Integer>> collection) {
    final Collection<Set<Integer>> processedCollection = new ArrayList<>();
    // ITERATE OVER ALL SETS
    for (final Set<Integer> numberSet : collection) {
        for (final Integer number : numberSet) {
            boolean matched = false;
            // ITERATE OVER ALL PROCESSED SETS COLLECTION
            for (final Set<Integer> processedSet : processedCollection) {
                // CHECK OF THERE IS A MATCH
                if (processedSet.contains(number)) {
                    matched = true;
                    // MATCH FOUND, MERGE THE SETS
                    processedSet.addAll(numberSet);
                    // BREAK OUT OF PROCESSED COLLECTION LOOP
                    break;
                }
            }
            // IF NOT MATCHED THEN ADD AS A COLLECTION ITEM
            if (!matched) {
                processedCollection.add(new HashSet<>(numberSet));
            }
        }
    }
    return processedCollection;
}

这是它的执行方式：

public static void main(String[] args) {
        final Collection<Set<Integer>> collection = new ArrayList<>();
        final Set<Integer> set1 = new HashSet<>();
        set1.add(1);
        set1.add(2);
        set1.add(3);
        collection.add(set1);

        final Set<Integer> set2 = new HashSet<>();
        set2.add(4);
        collection.add(set2);

        final Set<Integer> set3 = new HashSet<>();
        set3.add(1);
        set3.add(5);
        collection.add(set3);

        final Set<Integer> set4 = new HashSet<>();
        set4.add(4);
        set4.add(7);
        collection.add(set4);

        final Set<Integer> set5 = new HashSet<>();
        set5.add(3);
        set5.add(5);
        collection.add(set5);

        System.out.println(mergeIntersections(collection));

    }

- Ajay Deshwal

---

我怀疑这可以按要求工作。如果集合A与B和C相交，我没有看到任何机制可以防止AuBuC 和 BuC同时出现在输出列表中。此外，这似乎是O（某个大的）运行时间。 - Oliver Charlesworth

哦，没错，它改变了输入集。这是作弊 :/ - Oliver Charlesworth

感谢您的反馈，Oliver。我已经修复了这个变异。 - Ajay Deshwal

@AjayDeshwal 如果你有这样的输入 {1,2,3}, {2,5}, {4}，那么你期望在结果集合中得到两个集合 {1,2,3,5} 和 {4}，但是在你的解决方案中，结果集合会有三个集合，这是错误的。 - Mark

谢谢大家的建议。已经修复了这个场景。http://ideone.com/ilAMPD - Ajay Deshwal

Answer 2

这是我的实现。它从输入集合中删除所有集合，这可以通过先复制来轻松解决。它不会修改输入集合中的每个集合。使用我的实现，Ajay的主方法将打印[[1, 2, 3, 5], [4, 7]]。

Collection<Set<Integer>> filter(Collection<Set<Integer>> collection) {
    Collection<Set<Integer>> mergedSets = new ArrayList<>(collection.size());
    // for each set at a time, merge it with all sets that intersect it
    while (! collection.isEmpty()) {
        // take out the first set; make a copy as not to mutate original sets
        Set<Integer> currentSet = new HashSet<>(removeOneElement(collection));
        // find all intersecting sets and merge them into currentSet
        // the trick is to continue merging until we find no intersecting
        boolean mergedAny;
        do {
            mergedAny = false;
            Iterator<Set<Integer>> it = collection.iterator();
            while (it.hasNext()) {
                Set<Integer> candidate = it.next();
                if (intersect(currentSet, candidate)) {
                    it.remove();
                    currentSet.addAll(candidate);
                    mergedAny = true;
                }
            }
        } while (mergedAny);
        mergedSets.add(currentSet);
    }
    return mergedSets;
}

private static Set<Integer> removeOneElement(Collection<Set<Integer>> collection) {
    Iterator<Set<Integer>> it = collection.iterator();
    Set<Integer> element = it.next();
    it.remove();
    return element;
}

/** @return true if the sets have at least one element in common */
private static boolean intersect(Set<Integer> leftSet, Set<Integer> rightSet) {
    // don’t mutate, take a copy
    Set<Integer> copy = new HashSet<>(leftSet);
    copy.retainAll(rightSet);
    return ! copy.isEmpty();
}

- Ole V.V.

---

如果性能很重要，而且您的成员数量不是太大（比如1到100或者1到1000），那么您需要考虑使用java.util.BitSet来开发更高效的实现。 - Ole V.V.

一个重要的注释！我建议你将这个注释复制到你的答案中。 - Arvind Kumar Avinash

Answer 3

解决这个问题的一种优雅的方法是使用无向图，其中您将输入集合中的一个元素与同一集合中至少另一个元素连接起来，然后寻找连通组件。

因此，您的示例的图形表示如下：

从中我们可以轻松推断出连通组件：{1、2、3、5}和{4、7}。

这是我的代码：

Collection<Set<Integer>> filter(Collection<Set<Integer>> collection) {

    // Build the Undirected Graph represented as an adjacency list
    Map<Integer, Set<Integer>> adjacents = new HashMap<>();
    for (Set<Integer> integerSet : collection) {
        if (!integerSet.isEmpty()) {
            Iterator<Integer> it = integerSet.iterator();
            int node1 = it.next();
            while (it.hasNext()) {
                int node2 = it.next();

                if (!adjacents.containsKey(node1)) {
                    adjacents.put(node1, new HashSet<>());
                }
                if (!adjacents.containsKey(node2)) {
                    adjacents.put(node2, new HashSet<>());
                }
                adjacents.get(node1).add(node2);
                adjacents.get(node2).add(node1);
            }
        }
    }

    // Run DFS on each node to collect the Connected Components
    Collection<Set<Integer>> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    for (int start : adjacents.keySet()) {
        if (!visited.contains(start)) {
            Set<Integer> resultSet = new HashSet<>();
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(start);
            while (!stack.isEmpty()) {
                int node1 = stack.pop();
                visited.add(node1);
                resultSet.add(node1);
                for (int node2 : adjacents.get(node1)) {
                    if (!visited.contains(node2)) {
                        stack.push(node2);
                    }
                }
            }
            result.add(resultSet);
        }
    }

    return result;
}

- Helder Pereira

---

我不知道为什么每个人都提供完整的逐字逐句解决方案来回答这个问题。这不是 Stack Overflow 应有的风格。 - Oliver Charlesworth

@OliverCharlesworth 因为这很有趣 - David Pérez Cabrera

Answer 4

在我看来，最好的解决方案是 并查集算法

一个实现：

public class UnionFind {

    Set<Integer> all = new HashSet<>();
    Set<Integer> representants = new HashSet<>();
    Map<Integer, Integer> parents = new HashMap<>();

    public void union(int p0, int p1) {
        int cp0 = find(p0);
        int cp1 = find(p1);
        if (cp0 != cp1) {
            int size0 = parents.get(cp0);
            int size1 = parents.get(cp1);
            if (size1 < size0) {
                int swap = cp0;
                cp0 = cp1;
                cp1 = swap;
            }
            parents.put(cp0, size0 + size1);
            parents.put(cp1, cp0);
            representants.remove(cp1);
        }
    }

    public int find(int p) {
        Integer result = parents.get(p);
        if (result == null) {
            all.add(p);
            parents.put(p, -1);
            representants.add(p);
            result = p;
        } else if (result < 0) {
            result = p;
        } else {
            result = find(result);
            parents.put(p, result);
        }
        return result;
    }

    public Collection<Set<Integer>> getGroups() {
        Map<Integer, Set<Integer>> result = new HashMap<>();
        for (Integer representant : representants) {
            result.put(representant, new HashSet<>(-parents.get(representant)));
        }
        for (Integer value : all) {
            result.get(find(value)).add(value);
        }
        return result.values();
    }

    public static Collection<Set<Integer>> filter(Collection<Set<Integer>> collection) {
        UnionFind groups = new UnionFind();
        for (Set<Integer> set : collection) {
            if (!set.isEmpty()) {
                Iterator<Integer> it = set.iterator();
                int first =  groups.find(it.next());
                while (it.hasNext()) {
                    groups.union(first, it.next());
                }
            }
        }
        return groups.getGroups();
    }
}

- David Pérez Cabrera