algorithm - 在 Scala 中识别具有公共元素的命名集的有效方法

Question

给定一个 Map[String, Set[String]] 在 Scala 中，确定所有不同键对的集合，其中相应集合具有非空交集，什么是优雅而有效的方法？

例如将地图固定为

  val input = Map (
    "a" -> Set("x", "z"),
    "b" -> Set("f")
    "c" -> Set("f", "z", "44")
    "d" -> Set("99")
  )

那么所需的输出是

  Set(
    ("a", "c"),
    ("b", "c")
  )

在这种情况下，高效意味着比 O(n^2) 更好，其中 n 是作为输入给出的集合族中元素数量的总和。

score 2 · Accepted Answer

您无法获得比 O(n^2) 更好的悲观复杂度。看下面的例子：

Map(
  1 -> Set("a"),
  2 -> Set("a"),
  3 -> Set("a"),
  ...
  n -> Set("a")
)

在这种情况下，每一对集合都有非空交集。所以在这种情况下输出的大小是 O(n^2)，所以你不能得到更好的复杂度。

显然，这并不意味着你想不出比蛮力更好的算法。例如，您可以转换它：

val input = Map (
  "a" -> Set("x", "z"),
  "b" -> Set("f")
  "c" -> Set("f", "z", "44")
  "d" -> Set("99")
)

进入这个：

val transformed = Map (
  "x" -> Set("a"),
  "z" -> Set("a", "c"),
  "f" -> Set("b", "c"),
  "44" -> Set("c"),
  "99" -> Set("d")
)

您可以在线性时间内完成此操作。我会为此使用 Scala 集合构建器或可变集合，以避免对不可变集合进行昂贵的操作。

然后，您可以只查看这个转换后的映射中作为值的每个集合，并为每个集合生成所有可能的元素对。这可能需要 O(n^2) 但如果你的输出中没有很多对，那么它会快得多。

1 回答 1