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.

Agemen · Accepted Answer · 2014-10-01T16:11:04.793

6

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

edited Oct 01 '14 at 16:11

answered Oct 01 '14 at 16:02

Agemen

1,525
9
18

This seems perfect but the sub Lists are reversed. What does the `h::q` statement means? – Marco Oct 01 '14 at 16:24
1

Why do you need Math.abs if it's sorted? n will always be larger than last.head? – The Archetypal Paul Oct 01 '14 at 16:57
@Paul : Some kind of reflex I think. – Agemen Oct 01 '14 at 21:32
1

user3729739 : h :: q matches the List splitting it in two parts : its head (h, the first element of the list) and its tail (q, the list obtained by taking last and removing its first element) – Agemen Oct 01 '14 at 21:34
@Agemen thanks for the answer and the explanation. I guess that in order to have the sub-Lists ordered we would have to use the operator :+ but that is adding too much complexity (O(n)) to the function, right? – Marco Oct 01 '14 at 22:50
Honestly I think it will depend on the kind of list you are using. In a double linked list that shouldn't matter I think. – Agemen Oct 02 '14 at 07:39

score 0 · Answer 2 · answered Oct 01 '14 at 18:36

The cleanest answer would rely upon a method that probably should be called groupedWhile which would split exactly where a condition was true. If you had this method, then it would just be

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

But we don't have groupedWhile.

So let's make one:

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 generic capability, you can get the specific one easily.

Group List elements with a distance less than x

2 Answers2