CODEWITHSUNDEEP
javacollectionsset
Relative0
Relative0

Reputation: 1777

Unions and Intersections of Sets of Sets in Java (Generated Topology)

I am trying to test a possible Topology which is a set of open sets. To do this I need to find the unions and intersections of sets. In doing so I can create a Generated Topology. The best I think I can find, at least without having to use an external library - seems Google has a Guava library with Multiset capabilities, is to do something such as the following (last answer):

Set<Set<String>> myCollection = new HashSet<>();

I don't know if it is worth to try to learn the various methods for Multiset when I could somehow just loop through and add sets to "myCollection". Any advice on what the benefits really are for using something such as Multiset or Bag?

More specifically I would have a set (superset) of subsets, say for example {{A,B,D}, {B,C}} which we can see {A,B,D} U {B,C} = {A,B,C,D} and ${A,B,D} ∩ {B,C} = {B}$ hence the new superset of {{A,B,D}, {B,C}, {B}, {A,B,C,D}}. The supersets are not going to get very big, maybe a few dozen elements at most.

Upvotes: 1

Views: 1678

Answers (2)

sprinter
sprinter

Reputation: 27966

If I understand your question correctly you want a method that receives a set of sets and adds any sets that are the union of one or more of the members or the intersection of one or more of the members.

If that is correct then it can certainly be done with standard Java - no need for Guava or other libraries.

Writing methods to find the union or intersection is fairly trivial:

Set<T> union(Set<Set<T>> sets) {
    return sets.stream().reduce(new HashSet<>(), 
        (s1, s2) -> {
            s1.addAll(s2);
            return s1;
        });
}

Intersection is slightly harder: you need to copy the sets to avoid changing them:

Set<T> intersection(Set<Set<T>> sets) {
    return sets.stream().map(HashSet::new).reduce(
        (s1, s2) -> {
            s1.retainAll(s2);
            return s1;
        });
}

And the more complicated bit: performing these operations on all combinations of members. 

void topology(Set<Set<T>> sets) {
    process(new HashSet<>(sets), sets);
}

private void process(Set<Set<T>> input, Set<Set<T>> output) {
    if (!input.isEmpty()) {
        output.add(union(input));
        output.add(intersection(input));
        input.stream().forEach(el1 -> 
            process(input.stream().filter(el2 -> !el1.equals(el2))
                .collect(toSet()), output));
    }
}

Let me know in the comments if you need further explanation of these methods.

I tried this with the set {{1, 3, 5}, {2, 3, 7}, {4, 7, 9}} and received the result:

[[], [1, 2, 3, 5, 7], [3], [4, 7, 9], [7], [1, 3, 5], [2, 3, 4, 7, 9], [2, 3, 7], [1, 3, 4, 5, 7, 9], [1, 2, 3, 4, 5, 7, 9]]

I presume by your definition of the problem that you want the empty set in the result because the first and last elements of the original set do not overlap.

Upvotes: 0

Jacob G.
Jacob G.

Reputation: 29700

A Multiset is useful for when you require a Set that can contain multiple of the same element (as a Set can only hold one of each element).

If you're looking to find the union or intersection of multiple Sets, then I do recommend using Google's Guava library, as it has the following methods that will be useful to you in Sets.java:

static <E> Sets.SetView<E> union(Set<? extends E> set1, Set<? extends E> set2)
static <E> Sets.SetView<E> intersection(Set<E> set1, Set<?> set2)

If you'd rather not use Guava, then there are ways that you can find both the union and intersection of two sets in Java:

Set<Integer> first = new HashSet<>(Arrays.asList(1, 3, 5, 7));
Set<Integer> second = new HashSet<>(Arrays.asList(2, 4, 6, 8));

// Creates a new Set as a copy of 'first' and then adds every element from 'second' into the new Set, creating a union.
Set<Integer> union = new HashSet<>(first);

union.addAll(second);

System.out.println(union);

>> {1, 2, 3, 4, 5, 6, 7, 8}

// Creates a new Set as a copy of 'first' and then removes every element from the new Set that is not contained within 'second', creating an intersection.
Set<Integer> intersection = new HashSet<>(first);

intersection.retainAll(second);

System.out.println(intersection);

>> {}

Upvotes: 1

Related Questions