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

Question

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

例如将 map 固定为

  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 是作为输入给出的集合族中元素数量的总和。

Answer 1

您无法获得比 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)，但如果您的输出中没有很多对，那么它会快得多。