find intersection between multiple sets

Question

I have different sets that are named. Each set contains different number of Strings. I want to find out which set intersects with which. I have written the following algorithm(untested)

//initial structure key= set name, value = actual set
Map<String, Set<String>> namedSets = new LinkedHashMap<String, Set<String>>();

//get a list of all sets 
List<Set<String>> sets = new ArrayList<Set<String>>(namedSets.values());
List<String> names = new ArrayList<String>(namedSets.keySet());

while (!sets.isEmpty()){
    Set<String> examinedSet = sets.remove(0); //remove it because it will be checked sortly. 
    String name = names.remove(0); //remove its name too.
    //check it with remaining sets
    for (Set<String> set : sets){
        //there are common elements inside the two sets, 
        if (!Collections.disjoint(examinedSet, set)
            addIntersection(name, names.get(names.indexOf(set)));
    }

public void addIntersection(name, intersectedName){
    if (conflictedSets.containsKey(name){
        conflictedSets.get(name).add(intersectedName);

    }else{
        List<String> intersectedNames = new ArrayList<String>();
        intersectedNames.add(intersectedName);
        conflictedSets.put(name, intersectedNames);
    }
}

I don't like the fact that I have to do this nested loop, although for its iteration it is done for one loop less since the checked name gets removed from the list. Is there a more efficient way? My problem is that I don't wan't to check if they are intersecting but which one is intersecting with which. Is there a more efficient algorithm? }

possible duplicate of http://stackoverflow.com/questions/3590677/how-to-union-intersect-difference-and-reverse-data-in-java — Sharon Ben Asher, Dec 17 '15 at 14:03

score 0 · Answer 1 · answered Dec 17 '15 at 14:44

How about something like this? Sorry it's not too much Java8. However the idea is to put all the content into a hashtable and then consider elements which contains at least 1 common element as intersecting. I tested with this and it works. This does not scale well because of memory, so if your sets contain millions of entry it might not be the best choice. However it runs in O(N) time, with N being the number of entries in all your sets. I am also assuming N << number of sets.

import java.util.*;

class Main {
  public static void main(String[] args) {

    // Just adding data here

    Set<String> set1 = new HashSet<>();
    set1.add("a"); set1.add("b"); set1.add("c"); 

    Set<String> set2 = new HashSet<>();
    set2.add("a"); set2.add("z"); set2.add("j"); 

    Set<String> set3 = new HashSet<>();
    set3.add("n"); set3.add("d"); set3.add("f"); 

    //initial structure key= set name, value = actual set
    Map<String, Set<String>> namedSets = new LinkedHashMap<String, Set<String>>();

    namedSets.put("set1", set1);
    namedSets.put("set2", set2);
    namedSets.put("set3", set3);

    // Real code
    Map<String, ArrayList<Set<String>>> hashInter = new HashMap<>();
    Set<Map.Entry<Set<String>, Set<String>>> result = new HashSet<>();

    for (Map.Entry<String, Set<String>> entry : namedSets.entrySet()) {
        for (String s : entry.getValue()) {
            if (!hashInter.containsKey(s)) {
                hashInter.put(s, new ArrayList<Set<String>>());
            }

            hashInter.get(s).add(entry.getValue());

        }
    }


    for (Map.Entry<String, ArrayList<Set<String>>> entry : hashInter.entrySet()) {
        ArrayList<Set<String>> vals = entry.getValue();

        for (int i = 0; i < vals.size(); i++) {
            for (int j = 0; j < vals.size(); j++) {
                if (i >= j) {
                    continue;
                }
                Map.Entry<Set<String>, Set<String>> entryInter = new AbstractMap.SimpleEntry<Set<String>, Set<String>>(vals.get(i), vals.get(j));
                result.add(entryInter);
            }
        }
    }

    result.stream().forEach(e -> System.out.println(e.getValue() + " " + e.getKey()));
  }
}

yields

[a, z, j] [a, b, c]

find intersection between multiple sets

1 Answers1