Return list of relations between pairs lists using scala

Question

I have a case class that has two fields, names and lastNames:

case class Pair(names: List[Strin], lastNames: List[String])

now I have a list of this case class, but each list will have only 1 element:

val pair1 = Pair(List("john"), List("goldenberg")) 
val pair2 = Pair(List("george"), List("loyd"))
val pair3 = Pair(List("mark"), List("loyd"))
val pair4 = Pair(List("john"), List("buffet"))
val pair5 = Pair(List("ben"), List("goldenberg"))
val pair6 = Pair(List("ken"), List("rover"))

val pairings = List(pair1, pair2, pair3, pair4, pair5, pair6)

I was wondering if there is a nice way in scala to take the list of pairings and return list of pairings that will represent the parings as their relations, for example:

many:many
names: List("john", "ben") // john is with goldenberg and also goldenberg is with ben
lastNames: List("goldenberg", "buffet") // goldenberg is with ben and john, and also john is with buffet 

many:1
names: List("george", "mark") // george and mark are with loyd
lastNames: List("loyd")

1:1
names: List("ken") // ken is with rover
lastNames: List("rover")

so the result will be:

resPairings = List(
Pair(names = List("john", "ben"), lastNames = List("goldenberg", "buffet")),
Pair(names = List("george", "mark"), lastNames = List("loyd")),
Pair(names = List("ken"), lastNames = List("rover")),
)

Answer 1

Let's think about the following algorithm:

Take the first Pair, and consolidate all pairs that we know should be paired with him. If this group is not empty, then we need to do another cycle of that first pair. Because the consolidation could have exposed us to knew pairs to be consolidated with. Once we got a pair that cannot be consolidated with any other pair, we know it is a "final" pair, and that we can start calculating the next one.

You can try the following:

def merge(pair: Pair, other: List[Pair]): Pair = {
  Pair((pair.names ++ other.flatMap(_.names)).distinct, (pair.lastNames ++ other.flatMap(_.lastNames)).distinct)
}    

def consolidatePairings(pairs: List[Pair]): List[Pair] = pairs match {
  case List() => List()
  case List(pair) => List(pair)
  case pairToCompare :: otherPairs =>
    val (toConsolidate, toNotConsolidate) = otherPairs.partition(otherPair => pairToCompare.lastNames.intersect(otherPair.lastNames).nonEmpty || pairToCompare.names.intersect(otherPair.names).nonEmpty)
    val consolidatedPair = merge(pairToCompare, toConsolidate)
    if (toConsolidate.isEmpty) {
      consolidatedPair :: consolidatePairings(toNotConsolidate)
    } else {
      consolidatePairings(consolidatedPair :: toNotConsolidate)
    }
}

than the call consolidatePairings(pairings) will result with:

List(Pair(List(john, ben),List(goldenberg, buffet)), Pair(List(george, mark),List(loyd)), Pair(List(ken),List(rover)))

You can find this code in scastie.

Answer 2

Take the pairings list, as described in the question, and make a pair of interrelated Maps from it.

//translate the pairings List into 2 interrelated Maps
val (fnMap,lnMap) = pairings
  .foldLeft(Map.empty[String,List[String]].withDefaultValue(Nil) ->
    Map.empty[String,List[String]].withDefaultValue(Nil)){
    case ((fnm,lnm),Pair(fns,lns)) =>
      (fns.foldLeft(fnm){case (m,n) => m + (n -> (m(n) ++ lns))}
      ,lns.foldLeft(lnm){case (m,n) => m + (n -> (m(n) ++ fns))})
  }

The maps are both Map[String,List[String]]. They are interrelated in that every List element in one is also a key element in the other.

Now for the meat of the matter.

//given 2 Maps, unravel their relationships
@annotation.tailrec
def unravel(aMap :Map[String,List[String]]
           ,bMap :Map[String,List[String]]
           ,todo :List[String] = Nil
           ,acc  :List[Pair] = Nil) :List[Pair] = todo match {
  case a :: as =>                     //todo list not empty
    val bs = aMap(a)                  //get list of b values
    val Pair(fns, lns) :: accTl = acc //get top Pair from acc
    unravel(aMap - a                  //recurse, aMap minus 1
           ,bs.foldLeft(bMap)(_-_)    //bMap minus all of bs
           ,as ++ bs.flatMap(bMap).filter(_ != a) //add to todo
           ,Pair((a::fns).distinct, (lns++bs).distinct) :: accTl)

  case Nil if aMap.nonEmpty => //todo list is empty, aMap isn't
    val (a, bs) = aMap.head    //pop aMap
    unravel(aMap.tail                       //recurse, aMap less 1
           ,bs.foldLeft(bMap)(_-_)          //bMap minus all of bs
           ,bs.flatMap(bMap).filter(_ != a) //create new todo list
           ,Pair(List(a), bs) :: acc)       //push new Pair on acc

  case _ => acc  //all done
}

Make it happen.

unravel(fnMap, lnMap)
//res0: List[Pair] = List(
//   Pair(List(ken),List(rover))
// , Pair(List(john, ben),List(goldenberg, buffet))
// , Pair(List(mark, george),List(loyd))
//                       )

Explained

How to handle a many-to-many relationship? An aMap key might reference a long List of b values and each of those b keys might reference multiple a values, and so on, back and forth.

I decided to start by creating a new Pair instance made from one aMap key and its List of b values. If any of those b keys reference yet unresolved a values then those are placed in a todo list.

With each recursion the todo list is checked first. If the list isn't empty then one element is pulled from it and the most recent Pair instance is updated with the a -> List(b,...) data.

Repeat until both the todo list and the aMap map are empty.

Answer 3

Personally I would transform you representation into:

val nameToSurnames: Map[String, List[String]] = pairings
  .flatMap { case Pair(ks, vs) => ks.map(k => k -> vs) }
  .groupMap(_._1)(_._2)
  .view
  .mapValues(_.flatten)
  .toMap

val surnameToNames: Map[String, List[String]] = pairings
  .flatMap { case Pair(vs, ks) => ks.map(k => k -> vs) }
  .groupMap(_._1)(_._2)
  .view
  .mapValues(_.flatten)
  .toMap

Both maps should help to generate whatever representation you want e.g. by checking how big is result returned by a map for a key.