CODEWITHSUNDEEP
scalacollections
x89a10
x89a10

Reputation: 691

Built-in method for complex grouping of elements in a scala collection

I'm working on a problem where I need to group the items in a Scala collection by using a non-transitive predicate function. As an example, I might have a Set(52**, 521*, 5211, 5212) and also 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

The stars are basically wildcards and can be equal to anything.

The result of grouping should look like:

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

Notice how the predicate holds true for all the items grouped together. I'm hoping to learn if there is a built-in method that can help achieve such behavior.

The predicate function is commutative.

Upvotes: 3

Views: 115

Answers (1)

Aivean
Aivean

Reputation: 10882

Assuming that your "predicate" can be arbitrary function, there is bruteforce solution using Scala built-in methods. It just generates all combinations of elements and checks every pair of elements within the combination against 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 bruteforce, hence very inefficient. Knowing more about your predicate function, possible elements and input size will help to come up with more efficient solution.

Upvotes: 2

Related Questions