Built-in method for complex grouping of elements in a scala collection
I am working on an issue where I need to group elements in a Scala collection using a non-transitive predicate function. For example, I could have Set(52**, 521*, 5211, 5212)
as well as have:
predicate(52**, 521*) = true
predicate(52**, 5211) = true
predicate(52**, 5212) = true
predicate(521*, 5211) = true
predicate(521*, 5212) = true
predicate(5211, 5212) = false
Stars are basically wildcards and can be equal to anything.
The grouping result should look like this:
Set(Set(52**,521*,5211), Set(52**,521*,5212))
Note that the predicate is true for all items grouped together. I'm hoping to see if there is a built-in method that can help achieve this behavior.
The predicate function is commutative.
source to share
Assuming your "predicate" could be an arbitrary function, there is a bruteforce solution using Scala's built-in methods. It just generates all combinations of elements and checks every pair of elements within the combination for 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))
Result:
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))
As I said, this approach is brute force and therefore very ineffective. Knowing more about your function predicate
, the possible elements and the size of the input will help you find a more efficient solution.
source to share