Group elements in a list by range Scala

Question

Considering the following List in Scala :

List(4, 5, 6, 7, 8, 12, 13, 14, 17, 23, 24, 25)

I want to get the output

List(List(4,8), List(12,14), List(17), List(23,25))

I have this answer Scala List function for grouping consecutive identical elements

But it is working for grouping identical elements in the same List.

How to extend this solution to resolve my current problem?

I have tried this code

def sliceByRange[A <% Int](s: List[A]): List[List[A]] = s match {
      case Nil => Nil
     case x :: xs1 =
    val (first, rest) = s.span(y => y - x == 1)
    first :: sliceByRange(rest)
    }

But it is not working.

What problems did you run into when you have implemented it yourself? — Dima
– Dima, Commented Jul 13, 2016 at 11:51
A little bit trickier case than usual, no solutions at all after 20 mins :) — Nikita
– Nikita, Commented Jul 13, 2016 at 11:56

ziggystar · Accepted Answer · 2017-09-18 06:53:28Z

1

Tail-recursive solution

Code

Note that you could also use List[(Int,Int)] as result type instead of List[List[Int]]. This would reflect the fact that the result is a List of ranges more appropriately. Of course then you couldn't turn List(x,x) into List(x) for singleton ranges. But I expect that this will come back to bite you later anyway.

import scala.annotation.tailrec

@tailrec
def split(in: List[Int], acc: List[List[Int]] = Nil): List[List[Int]] = (in,acc) match {
  case (Nil,a) => a.map(_.reverse).reverse
  case (n :: tail, (last :: t) :: tt) if n == last + 1 => split(tail, (n :: t) :: tt)
  case (n :: tail, a ) => split(tail, (n :: n :: Nil) :: a)
}

val result = split(List(4, 5, 6, 7, 8, 12, 13, 14, 17, 23, 24, 25))
println(result)

println("removing duplicates:")
println(result.map{
  case List(x,y) if x == y => List(x)
  case l => l
})

Output

List(List(4, 8), List(12, 14), List(17, 17), List(23, 25))
removing duplicates:
List(List(4, 8), List(12, 14), List(17), List(23, 25))

edited Sep 18, 2017 at 6:53

answered Jul 13, 2016 at 12:54

ziggystar

28.7k9 gold badges76 silver badges127 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Toby Over a year ago

This doesn't seem to work as shown:

scala> split(List(4, 5, 6, 7, 8, 12, 13, 14, 17, 23, 24, 25)) res2: List[List[Int]] = List(List(4, 8), List(12, 12), List(13, 13), List(14, 14), List(17, 17), List(23, 23), List(24, 24), List(25, 25))

Am I missing something?

ziggystar Over a year ago

@Toby Thanks, I introduced a bug on a later edit. It's fixed now.

insan-e · Accepted Answer · 2016-07-13 14:17:39Z

Here is another example:

val myList = List(4, 5, 7, 8, 12, 13, 14, 17, 23, 24, 25)

def partition(list: List[Int]): (List[Int], List[Int]) = {
    val listPlusOne = (list.head - 1 :: list) // List(1,2,5) => List(0, 1, 2, 5)
    val zipped = list zip listPlusOne // zip List(1,2,5) with List(0, 1, 2, 5) => List((1,0), (2,1), (5,2))

    val (a, b) = zipped span { case (a, b) => b + 1 == a } // (List((1,0), (2,1)), List((5,2)))
    (a.map(_._1), b.map(_._1)) // (List(1, 2),List(5))
}

def group(list: List[Int]): List[List[Int]] = list match {
    case Nil => Nil
    case _ =>
        val (a, b) = partition(list)
        val listA =  List(List(a.head, a.last).distinct) // remove middle numbers..
        val listB = if (b.isEmpty) Nil else group(b)
        listA ++ listB
}

println(group(myList))

A bit more complicated, but it works...

Tzach Zohar · Accepted Answer · 2016-07-13 12:05:15Z

0

Paraphrasing the answer of the question you referenced:

def split(list: List[Int]) : List[List[Int]] = list match {
  case Nil => Nil
  case h::t =>
    val segment = list.zipWithIndex.takeWhile { case (v, i) => v == h+i }.map(_._1)
    List(h, segment.last).distinct :: split(list drop segment.length)
}

Using zipWithIndex to check for each element whether it's exactly the "next" integer (number should increase "together" with the index). Then - taking only the "boundaries" of the segment and recursively moving on to the rest of the list.

answered Jul 13, 2016 at 12:05

Tzach Zohar

37.9k3 gold badges83 silver badges86 bronze badges

Comments

Alex Elkin · Accepted Answer · 2019-04-03 13:10:12Z

My solution:

def sliceByRange(items: List[Int]) =
  items.sorted.foldLeft(Nil: List[List[Int]]) {
    case (initRanges :+ (head :: Nil), next) if head == next - 1 =>
      initRanges :+ (head :: next :: Nil) // append element to the last range
    case (initRanges :+ (head :: last :: Nil), next) if last == next - 1 =>
      initRanges :+ (head :: next :: Nil) // replace last range
    case (ranges, next) =>
      ranges :+ (next :: Nil) // add new range
  }

Usage:

sliceByRange(List(1, 2, 3, 5, 8, 9, 12, 13, 14, 19))
// List(List(1, 3), List(5), List(8, 9), List(12, 14), List(19))

If you wish to keep middle values you can use the following example:

def makeSegments(items: List[Int]) =
  items.sorted.foldLeft(Nil: List[List[Int]]) {
    case (initSegments :+ lastSegment, next) if lastSegment.last == next - 1 =>
      initSegments :+ (lastSegment :+ next)
    case (segments, next) =>
      segments :+ (next :: Nil)
  }

Usage:

makeSegments(List(1, 2, 3, 5, 8, 9, 12, 13, 14, 19))
// List(List(1, 2, 3), List(5), List(8, 9), List(12, 13, 14), List(19))

When range size at least 3 elements:

def sliceByRange3elements(items: List[Int]) =
  items.sorted.foldLeft(Nil: List[List[Int]]) {
    case (initRanges :+ (head :: last :: Nil), next) if last == next - 1 =>
      initRanges :+ (head :: next :: Nil) // replace last range
    case (initRanges :+ (ll :: Nil) :+ (l :: Nil), next) if ll == next - 2 && l == next - 1 =>
      initRanges :+ (ll :: next :: Nil) // make new range
    case (ranges, next) =>
      ranges :+ (next :: Nil)
  }

Usage (note that (8,9) are not range now):

sliceByRange3elements(List(1, 2, 3, 5, 8, 9, 12, 13, 14, 19))
// List(List(1, 3), List(5), List(8), List(9), List(12, 14), List(19))

You can define printRanges method to more visual output:

def printRanges(ranges: List[List[Int]]) =
  ranges.map({
    case head :: Nil => head.toString
    case head :: last :: Nil => s"$head-$last"
    case _ => ""
  }).mkString(",")

printRanges(
  sliceByRange(List(1, 2, 3, 5, 8, 9, 12, 13, 14, 19)))
// 1-3,5,8-9,12-14,19

printRanges(
  sliceByRange3elements(List(1, 2, 3, 5, 8, 9, 12, 13, 14, 19)))
// 1-3,5,8,9,12-14,19

Collectives™ on Stack Overflow

Group elements in a list by range Scala

4 Answers 4

Tail-recursive solution

Code

Output

2 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Tail-recursive solution

Code

Output

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related