如何通过交集过滤集合集合？

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}.

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

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

    }