CODEWITHSUNDEEP
scalalistfunctional-programming
Munesh
Munesh

Reputation: 1569

How to convert a list to list of lists by group the elements when an element repeats in Scala idiomatic way

I want to convert a list of elements into a list of lists by breaking whenever an element repeats like below

Input:

List(1, 2, 3, 1, 2, 1, 3, 1, 2, 3)

Ouput:

List[List[Integer]] = List(List(1, 2, 3), List(1, 2), List(1, 3), List(1, 2, 3))

Here's what I've tried:

val tokens = List(1,2,3,1,2,1,3,1,2,3)

val group = new ListBuffer[List[Integer]]()
val nextGroup = new ListBuffer[Integer]()
val nextTokens = new ListBuffer[Integer]()

for (t <- tokens) {
  if (nextTokens.contains(t)) {
    group += nextGroup.toList
    nextGroup.clear()
    nextTokens.clear()
  }
  nextGroup += t
  nextTokens += t
}

group += nextGroup.toList

group.toList

I'm looking for a better way to achieve this using map/foldLeft... functions without using ListBuffer.

Thanks in advance.

Upvotes: 0

Views: 827

Answers (3)

Berthur
Berthur

Reputation: 4495

Here is a very direct solution which uses foldLeft while keeping track of two accumulator arrays: One for the final result, and one for the currently considered token sublist. Finally, we combine the result array with the last sublist.

val (acc, last) = tokens.foldLeft ((List[List[Int]](), List[Int]())) ((a,b) =>
            if (a._2.contains(b)) (a._1 :+ a._2, List(b))
            else (a._1, a._2 :+ b))
acc :+ last

Notice that this is not the computationally most efficient solution, since for each iteration we are checking through the entire sublist under consideration using contains. If you wish for efficiency, you might (depending on your data) consider an approach which uses hash maps or similar data structures instead for faster repetition checks.

Upvotes: 0

Munesh
Munesh

Reputation: 1569

Using the solution provided for below question, I have come up with the below solution

https://stackoverflow.com/a/52976957/1696418

mySeq.foldLeft(List.empty[List[Int]]) {
  case (acc, i) if acc.isEmpty => List(List(i))
  case (acc, i) if acc.last.contains(i) => acc :+ List(i)
  case (acc, i) => acc.init :+ (acc.last :+ i)
}

Upvotes: 0

Tim
Tim

Reputation: 27421

Here is a version using foldLeft

tokens
  .drop(1)
  .foldLeft(List(tokens.take(1))) { case (res, token) =>
    if (res.head.contains(token)) {
      List(token) +: res
    } else {
      (res.head :+ token) +: res.tail
    }
  }
  .reverse

Using drop and take ensures that this works on an empty list. Building the result in reverse means that the latest List is always at the head, and will also be efficient for long lists.

And for completeness, here is a recursive function that does the same thing:

def groupDistinct[T](tokens: List[T]): List[List[T]] = {
  @tailrec
  def loop(token: List[T], cur: List[T], res: List[List[T]]): List[List[T]] =
    token match {
      case Nil =>
        res :+ cur
      case head :: tail =>
        if (cur.contains(head)) {
          loop(tail, List(head), res :+ cur)
        } else {
          loop(tail, cur :+ head, res)
        }
    }

  loop(tokens, Nil, Nil)
}

Upvotes: 1

Related Questions