The intersection of all combinations of n lists

Question

Given an ArrayList of ArrayLists with size larger than 3

ArrayList<ArrayList<Integer>> lists = new ArrayLists<ArrayList<Integer>>();

I want to take 3 unique sub-lists, find their intersection, then repeat this process for all possible combinations. Here follows the pseudocode

public void generateIntersections(ArrayLists<ArrayList<Integer>> lists) {
    if (lists.size() > 3) {
        int n = lists.size();
        //number of combinations theoretically, `!` is wrong I know
        int numberOfCombinations = n! / (3!(n - 3)!);
        while (numberOfCombinations) {
            // unique items
            ArrayList<Integer> list 1 = lists.get(?);
            ArrayList<Integer> list 2 = lists.get(?);
            ArrayList<Integer> list 3 = lists.get(?);

            Set<Integer> = intersection(list1, list2, list3);
        }
    }
}

I am puzzled by this problem as I am not sure how to properly keep track of three counters while iterating. I am further blocked by properly implementing the concept of combination as opposed to permutation in this particular case.

I have tried many things but in every case, my code quickly builds up to nonsense. I suppose I am lacking some particular trick. Perhaps something involving HashSets?

Answer 1

Map of intersections of intersections in Java 7

Three steps of processing the original lists: first collect a map of intersections for each element Map<Integer,Set<Integer>>, then for this map collect a map of intersections of intersections Map<Set<Integer>,Set<Integer>>, and then append the larger intersections sets to the smaller intersections sets if they intersect.

Try it online!

Original lists List<List<Integer>>:

List 0: [1, 2, 6, 5, 4, 3]
List 1: [3, 7, 2, 9, 5, 4]
List 2: [2, 6, 7, 1, 4]

1 - Map of intersections Map<Integer,Set<Integer>>:

Element: 1 is in lists: [0, 2]
Element: 2 is in lists: [0, 1, 2]
Element: 3 is in lists: [0, 1]
Element: 4 is in lists: [0, 1, 2]
Element: 5 is in lists: [0, 1]
Element: 6 is in lists: [0, 2]
Element: 7 is in lists: [1, 2]
Element: 9 is in lists: [1]

2 - Map of intersections of intersections Map<Set<Integer>,Set<Integer>>:

Lists: [0, 1, 2] contain elements: [2, 4]
Lists: [0, 1] contain elements: [3, 5]
Lists: [0, 2] contain elements: [1, 6]
Lists: [1, 2] contain elements: [7]

3 - Map of intersections of intersections after appending the larger intersections sets to the smaller intersections sets if they intersect:

Lists: [0, 1, 2] contain elements: [2, 4]
Lists: [0, 1] contain elements: [2, 3, 4, 5]
Lists: [0, 2] contain elements: [1, 2, 4, 6]
Lists: [1, 2] contain elements: [2, 4, 7]

---

Java 7 code:

List<List<Integer>> lists = Arrays.asList(
        Arrays.asList(1, 2, 6, 5, 4, 3),
        Arrays.asList(3, 7, 2, 9, 5, 4),
        Arrays.asList(2, 6, 7, 1, 4));

// map of intersections:
// key - element of the list,
// value - set of indexes of lists,
// i.e. where this element occurs
Map<Integer, Set<Integer>> map1 = new TreeMap<>();
for (int i = 0; i < lists.size(); i++) {
    // output the original list
    System.out.println("List " + i + ": " + lists.get(i));
    for (int element : lists.get(i)) {
        // pull out the set of intersections
        Set<Integer> set = map1.remove(element);
        // create it if it doesn't exist
        if (set == null) set = new TreeSet<>();
        // add index of current list
        set.add(i);
        // put into the map
        map1.put(element, set);
    }
}

// intermediate output
for (Map.Entry<Integer, Set<Integer>> entry : map1.entrySet())
    System.out.println("Element: " + entry.getKey()
            + " is in lists: " + entry.getValue());

// custom comparator for the map of intersections of intersections
Comparator<Set<Integer>> comparator = new Comparator<Set<Integer>>() {
    @Override
    public int compare(Set<Integer> o1, Set<Integer> o2) {
        // group intersections that are equal
        if (o1.containsAll(o2) && o2.containsAll(o1)) return 0;
        // compare by number of intersections in reverse order
        int val = Integer.compare(o2.size(), o1.size());
        if (val != 0) return val;
        // if sizes are equal compare hashCodes
        return Integer.compare(o1.hashCode(), o2.hashCode());
    }
};

// map of intersections of intersections:
// key - set of indexes of lists
// value - set of elements
TreeMap<Set<Integer>, Set<Integer>> map2 = new TreeMap<>(comparator);
for (Map.Entry<Integer, Set<Integer>> entry : map1.entrySet()) {
    // set of intersecting elements
    Set<Integer> key = entry.getValue();
    // filter out unique elements
    if (key.size() == 1) continue;
    // pull out the set of intersecting elements
    Set<Integer> value = map2.remove(key);
    // create it if it doesn't exist
    if (value == null) value = new TreeSet<>();
    // add current element
    value.add(entry.getKey());
    // put into the map
    map2.put(key, value);
}

// intermediate output
for (Map.Entry<Set<Integer>, Set<Integer>> entry : map2.entrySet())
    System.out.println("Lists: " + entry.getKey()
            + " contain elements: " + entry.getValue());

// append the larger intersections sets to the
// smaller intersections sets if they intersect
for (Map.Entry<Set<Integer>, Set<Integer>> entry : map2.entrySet()) {
    // for each entry process the values of other
    // entries with less number of intersections
    Map<Set<Integer>, Set<Integer>> tailMap = map2.tailMap(entry.getKey(), false);
    for (Map.Entry<Set<Integer>, Set<Integer>> other : tailMap.entrySet())
        // if the intersection set of the current entry contains
        // all intersections from the set of another entry
        if (entry.getKey().containsAll(other.getKey()))
            // then add all intersecting elements of
            // the current entry to another entry
            other.getValue().addAll(entry.getValue());
}

// final output
for (Map.Entry<Set<Integer>, Set<Integer>> entry : map2.entrySet())
    System.out.println("Lists: " + entry.getKey()
            + " contain elements: " + entry.getValue());

---

^{See also: The intersection of all combinations of n sets}