How to check which of multiple given sets are disjoint?-CodePudding

I want to write a method that uses the standard for loop to iterate through a given set of sets, and returns a hashmap that the disjoint sets are added to. I'm aware that the does not work correctly, it's an example of how I've tried to solve this. How do I check the elements within the sets, also without the algorithm becoming too inefficient?

public <E> Map<Set<E>, Set<Set<E>>> disjointSets(Set<Set<E>> Sets) {
    Map<Set<E>, Set<Set<E>>> result = new HashMap<>();

    for (Set<E> x : Sets) {
        for (Set<E> y : Sets) {
            if (!x.equals(y)) {
                result.put(x, Sets);
            }
        }
    }
    return result;
}
/**
 * As an example, if input sets would be:
 * [0]
 * [0, 4, 5]
 * [1, 2]
 * -> expected output should be:
 * [0] : [ [1, 2] ]
 * [0, 4, 5] : [ [1, 2] ]
 * [1, 2] : [ [0] [0, 4, 5] ]
 */

CodePudding user response：

How do I check the elements within the sets

You can just cycle trough them and use Set.contains

for (Set<E> x : Sets) {
    for (Set<E> y : Sets) {
        boolean isDisjoint = true;
        for (E ey : y) {
            if (x.contains(ey)) {
                isDisjoint = false;
                break;
            }
        }
        ...

CodePudding user response：

You can generate a map of type Map<E,Set<Set<E>>> which associates each distinct element which might be found in these Sets with a group of Sets to which it belongs. This approach would allow to avoid redundant performing redundant iterations.

A disjoint Set that corresponds to each Set can be found in the following steps:

For each Set create a copy of the given Sets (that would be a value that corresponds to a particular set in the resulting map);
Iterate over the elements of a current Set and remove a value (denoted as disjoint in the code below) of all Sets to which a particular element belongs. A previously generated Map containing Sets associated with each distinct element would be handy for that.

In the code below, I've used Java 8 method computeIfAbsent(), which is concise and expressive (an alternative option provided in the comments):

public static <E> Map<Set<E>, Set<Set<E>>> disjointSets(Set<Set<E>> sets) {

    Map<E, Set<Set<E>>> containsElement = new HashMap<>();
    
    for (Set<E> set: sets) {
        for (E next: set) {
            containsElement   // alternatively you can use: containsElement.putIfAbsent()   containsElement.get()add()
                .computeIfAbsent(next, k -> new HashSet<>())
                .add(set);
        }
    }
    
    Map<Set<E>, Set<Set<E>>> result = new HashMap<>();
    
    for (Set<E> set: sets) {
        Set<Set<E>> disjoint = new HashSet<>(sets);
        result.put(Collections.unmodifiableSet(set), disjoint);
        
        for (E next: set) {
            disjoint.removeAll(containsElement.get(next));
        }
    }
    return result;
}

main()

public static void main(String[] args) {
    Set<Set<Integer>> sets = Set.of(
        Set.of(0), Set.of(0, 4, 5), Set.of(1, 2)
    );
    
    disjointSets(sets).forEach((element, disjoint) -> System.out.println(element   " -> "   disjoint));
}

Output:

[0] -> [[1, 2]]
[1, 2] -> [[0], [0, 5, 4]]
[0, 5, 4] -> [[1, 2]]

Time Complexity: O(n*m) (considering that we are given n sets containing m elements).