CODEWITHSUNDEEP
scala
Sim
Sim

Reputation: 4184

Efficiently combine two lists resulting in a set of new lists

I have two sets of lists:

A: {1 -> B -> 3, 4 -> B -> 5 }
B: { 7 -> 8 }

which I want to combine resulting in

A' : {1 -> 7 -> 8 -> 3, 4 -> 7 -> 8 -> 5 }

Note: There might be multiple references to B in the same list.

A: {B -> 1 -> B}
B: {2,3}
A' : {2 -> 1 -> 2, 2 -> 1 -> 3, 3 -> 1 ->2, 3 -> 1 -> 3}

My current approach is recursive and works on each of the individual lists of A:

object dummy {

    trait Step
    // I owe you referencing another set
    case class IOU(ref : String)
    // a simple step within the list
    case class Step(id : Long)

    def recursiveResolve(
                          id: String,
                          to: Set[Seq[Step]],
                          on: Seq[Step]): Set[Seq[Step]] = {
      on match {
          // here we are done and can return the empty set to resolve the recursion tree
        case Nil => Set()
          // we have still work left and now work on the first element remaining
        case mul :: tiple =>
          val step: Set[Seq[Step]] = mul match {
              // if we have an I owe you that references the replace in list
            case x: IOU if x.ref == id =>
              // return the replace in set of lists
              to
            case x => Set(Seq(x))
          }
          val next: Set[Seq[Step]] = recursiveResolve(id, to, tiple)
          // if the next step returned non empty we have to merge
          if (next.nonEmpty) {
            step.flatMap { elem: Seq[Step] =>
              next.map { nextElem: Seq[Step] =>
                elem ++ nextElem
              }
            } 
          } else {
            step
          }
      }
    }
  }

val A : Set[Seq[Step]] = Set( Seq( Step(1), IOU("B"), Step(3)), Seq( Step(4), IOU("B"), Step(5) ))
val B : Set[Seq[Step]] = Set( Seq(Step(7), Step(8) ) )
val result : Set[Seq[Step]] = A.flatMap(elem => recursiveResolve("B",B,elem))

This works but is obviously horribly inefficient as each step of the list involves consing and merging and flatMapping. Furthermore, the problem I am trying to solve involves larger lists, sometimes with multiple references per list to different or the same set.

Is there a more efficient approach?

Upvotes: 0

Views: 111

Answers (1)

Dima
Dima

Reputation: 40500

Ugh, yeah .. that becomes expensive (but still polynomial - I think, it's O(A*N*B^2))

 def resolve(bs: Set[Seq[Step]])(s: Seq[Step]): Set[Seq[Step]] =  s match {
  case Seq(IOU(_), tail@_*) => bs.flatMap { b =>  resolve(bs)(tail).map(b ++: _) }
  case Seq(head, tail@_*) => resolve(bs)(tail).map(head +: _)
  case Seq() => Set(Seq()) 
 }
 
 A.flatMap(resolve(B))

Upvotes: 2

Related Questions