n 个列表的所有组合的交集

Question

给定一个大小大于 3 的 ArrayList 的 ArrayList

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

我想取 3 个不同的子列表，找到它们的交集，然后对所有可能的组合重复此过程。下面是伪代码

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);
        }
    }
}

我对这个问题感到困惑，因为我不确定如何在迭代时正确地跟踪三个计数器。在这种特殊情况下，通过正确实施组合概念而不是排列，我进一步受阻。

我尝试了很多东西，但在每种情况下，我的代码很快就会变得毫无意义。我想我缺少一些特别的技巧。也许涉及 HashSets？

Answer 1

Java 7

中交叉点的交叉点地图

处理原始列表的三个步骤：首先为每个元素收集一个交点图Map<Integer,Set<Integer>>，然后为这个图收集一个交点的交点图Map<Set<Integer>,Set<Integer>>，然后追加较大的如果交叉点相交，则交叉点设置为较小的交叉点集。

Try it online!

原始列表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<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<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 - 将较大的交叉点集附加到较小的交叉点集后交叉点的交叉点地图（如果它们相交）：

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]

Java7代码：

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

^{另请参阅：The intersection of all combinations of n sets}

n 个列表的所有组合的交集

The intersection of all combinations of n lists

java

combinations

arraylist

set-intersection

Java 7