元素成对比较的高效算法

Question

给定一个包含一些键值对的数组：

[
  {'a': 1, 'b': 1},
  {'a': 2, 'b': 1},
  {'a': 2, 'b': 2},
  {'a': 1, 'b': 1, 'c': 1},
  {'a': 1, 'b': 1, 'c': 2},
  {'a': 2, 'b': 1, 'c': 1},
  {'a': 2, 'b': 1, 'c': 2}
]

我想找到这些对的交集。交叉意味着只留下那些可以被其他元素覆盖或唯一的元素。例如， {'a': 1, 'b': 1, 'c': 1}和{'a': 1, 'b': 1, 'c': 2}完全覆盖{'a': 1, 'b': 1}，而{'a': 2, 'b': 2}是唯一的。所以，在

[
  {'a': 1, 'b': 1},
  {'a': 2, 'b': 1},
  {'a': 2, 'b': 2},
  {'a': 1, 'b': 1, 'c': 1},
  {'a': 1, 'b': 1, 'c': 2},
  {'a': 2, 'b': 1, 'c': 1},
  {'a': 2, 'b': 1, 'c': 2}
]

找到路口后应保留

[
  {'a': 2, 'b': 2},
  {'a': 1, 'b': 1, 'c': 1},
  {'a': 1, 'b': 1, 'c': 2},
  {'a': 2, 'b': 1, 'c': 1},
  {'a': 2, 'b': 1, 'c': 2}
]

我尝试迭代所有对并找到相互比较的覆盖对，但时间复杂度等于O(n^2)。是否有可能在线性时间内找到所有覆盖或唯一对？

这是我的代码示例（O(n^2)）：

public Set<Map<String, Integer>> find(Set<Map<String, Integer>> allPairs) {
  var results = new HashSet<Map<String, Integer>>();
  for (Map<String, Integer> stringToValue: allPairs) {
    results.add(stringToValue);
    var mapsToAdd = new HashSet<Map<String, Integer>>();
    var mapsToDelete = new HashSet<Map<String, Integer>>();
    for (Map<String, Integer> result : results) {
      var comparison = new MapComparison(stringToValue, result);
      if (comparison.isIntersected()) {
        mapsToAdd.add(comparison.max());
        mapsToDelete.add(comparison.min());
      }
    }
    results.removeAll(mapsToDelete);
    results.addAll(mapsToAdd);
  }
  return results;
}

其中 MapComparison 是：

public class MapComparison {

    private final Map<String, Integer> left;
    private final Map<String, Integer> right;
    private final ComparisonDecision decision;

    public MapComparison(Map<String, Integer> left, Map<String, Integer> right) {
        this.left = left;
        this.right = right;
        this.decision = makeDecision();
    }

    private ComparisonDecision makeDecision() {
        var inLeftOnly = new HashSet<>(left.entrySet());
        var inRightOnly = new HashSet<>(right.entrySet());

        inLeftOnly.removeAll(right.entrySet());
        inRightOnly.removeAll(left.entrySet());

        if (inLeftOnly.isEmpty() && inRightOnly.isEmpty()) {
            return EQUALS;
        } else if (inLeftOnly.isEmpty()) {
            return RIGHT_GREATER;
        } else if (inRightOnly.isEmpty()) {
            return LEFT_GREATER;
        } else {
            return NOT_COMPARABLE;
        }
    }

    public boolean isIntersected() {
        return Set.of(LEFT_GREATER, RIGHT_GREATER).contains(decision);
    }

    public boolean isEquals() {
        return Objects.equals(EQUALS, decision);
    }

    public Map<String, Integer> max() {
        if (!isIntersected()) {
            throw new IllegalStateException();
        }
        return LEFT_GREATER.equals(decision) ? left : right;
    }

    public Map<String, Integer> min() {
        if (!isIntersected()) {
            throw new IllegalStateException();
        }
        return LEFT_GREATER.equals(decision) ? right : left;
    }

    public enum ComparisonDecision {
        EQUALS,
        LEFT_GREATER,
        RIGHT_GREATER,
        NOT_COMPARABLE,

        ;
    }
}

Answer 1

假设列表中的每个元素都是唯一的。（元素是具有键值对的对象。）对于每个唯一的键值对，存储包含它的列表元素集。按大小递增的顺序迭代元素。对于每个元素，通过查找包含它们的元素集并将该集与当前交集相交来搜索其键值对。如果交集大小小于 2（假定交集至少包含一个元素，这就是我们正在研究的元素），请尽早退出。根据数据，我们可能对这些集合使用位集（每个位代表排序列表中映射元素的索引），这可以通过并行比较执行交集。同样取决于数据，交叉点可以显着减少搜索空间。

Python代码：

import collections

def f(lst):
  pairs_to_elements = collections.defaultdict(set)

  for i, element in enumerate(lst):
    for k, v in element.items():
      pairs_to_elements[(k, v)].add(i)

  lst_sorted_by_size = sorted(lst, key=lambda x: len(x))

  result = []

  for element in lst_sorted_by_size:
    pairs = list(element.items())
    intersection = pairs_to_elements[pairs[0]]
    is_contained = True

    for i in range(1, len(pairs)):
      intersection = intersection.intersection(pairs_to_elements[pairs[i]])
      if len(intersection) < 2:
        is_contained = False
        break

    if not is_contained:
      result.append(element)

  return result

输出：

lst = [
  {'a': 1, 'b': 1},
  {'a': 2, 'b': 1},
  {'a': 2, 'b': 2},
  {'a': 1, 'b': 1, 'c': 1},
  {'a': 1, 'b': 1, 'c': 2},
  {'a': 2, 'b': 1, 'c': 1},
  {'a': 2, 'b': 1, 'c': 2}
]

for element in f(lst):
  print(element)

"""
{'a': 2, 'b': 2}
{'a': 1, 'b': 1, 'c': 1}
{'a': 1, 'b': 1, 'c': 2}
{'a': 2, 'b': 1, 'c': 1}
{'a': 2, 'b': 1, 'c': 2}
"""