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?
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.
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());