Group list items with distance less than x

Question

I am trying to find a way to group all the objects in a list depending on the distance x between the elements.

For example, if the distance is 1 , then

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

will 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 think there should be a cleaner solution.

Answer 1

You can try sorting your list and then use foldLeft. Basically something like this

  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 looks fine, but vice versa. If necessary, call "reverse", if necessary, in 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 

Answer 2

The cleanest answer will be based on a method that should probably be called groupedWhile , which will be split exactly where the condition was true. If you had this method, it would be simple

 def byDist(xs: List[Int], d: Int) = groupedWhile(xs.sorted)((l,r) => r - l <= d) 

But we do not have groupedWhile .

So, let's do one thing:

 def groupedWhile[A](xs: List[A])(p: (A,A) => Boolean): List[List[A]] = { val yss = List.newBuilder[List[A]] val ys = List.newBuilder[A] (xs.take(1) ::: xs, xs).zipped.foreach{ (l,r) => if (!p(l,r)) { yss += ys.result ys.clear } ys += r } ys.result match { case Nil => case zs => yss += zs } yss.result.dropWhile(_.isEmpty) } 

Now that you have the general capabilities, you can easily get specific information.