Group List elements with a distance less than x

Question

I'm trying to figure out a way to group all the objects in a list depending on an x distance between the elements.

For instance, if distance is 1 then

List(2,3,1,6,10,7,11,12,14)

would give

List(List(1,2,3), List(6,7), List(10,11,12), List(14))

I can only come up with tricky approaches and loops but I guess there must be a cleaner solution.

Answer 1

You may try to sort your list and then use a foldLeft on it. Basically something like that

  def sort = {
    val l = List(2,3,1,6,10,7,11,12,14)
    val dist = 1
    l.sorted.foldLeft(List(List.empty[Int]))((list, n) => {
      val last = list.head
      last match {
        case h::q  if Math.abs(last.head-n) > dist=> List(n) :: list
        case _ => (n :: last ) :: list.tail 
      }
    }
    )
  }

The result seems to be okay but reversed. Call "reverse" if needed, when needed, on the lists. the code becomes

    val l = List(2,3,1,6,10,7,11,12,14)
    val dist = 1
    val res = l.sorted.foldLeft(List(List.empty[Int]))((list, n) => {
       val last = list.head
       last match {
         case h::q  if Math.abs(last.head-n) > dist=> List(n) :: (last.reverse :: list.tail)
        case _ => (n :: last ) :: list.tail
      }
    }
).reverse