scala - 用于对 Scala 集合中的元素进行复杂分组的内置方法

Question

我正在解决一个问题，我需要使用非传递谓词函数对 Scala 集合中的项目进行分组。例如，我可能有一个 Set(52**, 521*, 5211, 5212) 并且还有:

predicate(52**, 521*) = true
predicate(52**, 5211) = true
predicate(52**, 5212) = true    
predicate(521*, 5211) = true
predicate(521*, 5212) = true
predicate(5211, 5212) = false

星星基本上是通配符，可以等于任何东西。

分组的结果应该是这样的:

Set(Set(52**,521*,5211), Set(52**,521*,5212))

注意谓词如何适用于组合在一起的所有项目。我希望了解是否有内置方法可以帮助实现这种行为。

谓词函数是可交换的。

Answer 1

假设您的“谓词”可以是任意函数，则可以使用 Scala 内置方法进行暴力破解。它只是生成元素的所有组合，并根据 predicate 检查组合中的每一对元素。

def predicate(s1:String, s2:String) =
  Map(
    Set("52**", "521*") -> true,
    Set("52**", "5211") -> true,
    Set("52**", "5212") -> true,
    Set("521*", "5211") -> true,
    Set("521*", "5212") -> true,
    Set("5211", "5212") -> false
  )(Set(s1,s2))

val input = List("52**", "521*", "5211", "5212")

val res = (2 to input.size).flatMap(input.combinations)
  .filter(_.combinations(2).forall {
  case Seq(x1, x2) => predicate(x1, x2)
}).map(_.toSet)

val maximalRes = res.filter(r => 
  !res.exists(x => x != r && r.diff(x).isEmpty))

结果:

res = Vector(Set(52**, 521*), Set(52**, 5211), Set(52**, 5212), Set(521*, 5211), Set(521*, 5212), Set(52**, 521*, 5211), Set(52**, 521*, 5212))
maximalRes = Vector(Set(52**, 521*, 5211), Set(52**, 521*, 5212))

正如我所说，这种方法是暴力破解，因此效率很低。详细了解您的 predicate 函数、可能的元素和输入大小将有助于提出更有效的解决方案。