如何按交集过滤集合？

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是相交的。我们可以将其重写为新的set {1,2,3,5}。我们也有两个集合，它们也有交集。它们是2和4，我们可以创建一个新的集合{4,7}。输出结果将是两个集合的集合：{1,2,3,5}和{4,7}。

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

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

    }

Answer 2

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

因此，您的示例的图形表示为：

​

​

由此我们可以很容易地推断出连通分量：{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;
}

Answer 3

我想最好的解决方案是Union-Find algorithm

一个实现：

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