Group by margin

I am having a sequence of Int numbers:

val numbers = Seq(5, 3, 4, 1)

I need to group them according to their difference. The difference has to be smaller or equal to a certain threshold, let it be 2 for this example. So the possible groups would be:

  • (5, 3, 4) (1)
  • (1, 3) (5, 4)

I don't really care which of these constellations of groups I'll get. Each element is allowed to be used once. I also need to remain the index, so prior grouping I would need a zipWithIndex.

Is there a clever way to do such grouping?

Answers


Ok then. Idea of the algorithm:

Take the next element in numbers. Check whether it belongs to a previously created group. If it does, add it to that group. If not, add a new group with the element. I use IndexedSeq because i want indexing to be O(1).

It is kinda long, but I can't think of something better at the moment. I hope I understood you correctly with your idea of "difference".

val numbers = Seq(5, 3, 4, 1)

def group(seq: Seq[Int], treshold: Int) = seq.zipWithIndex.foldLeft(IndexedSeq.empty[IndexedSeq[(Int,Int)]])((result, elem) =>  {
    (0 until result.size).find(
        i => result(i).forall(num => (num._1 - elem._1).abs <= treshold)).map(
            i => result.updated(i, result(i) :+ elem))
                .getOrElse(result :+ IndexedSeq(elem))
})

println(group(numbers, 2)) //result Vector(Vector((5,0), (3,1), (4,2)), Vector((1,3)))

Edit forgot you wanted to zipWithIndex


Since you're working with indices of elements anyway, you may not care about working with indices of the groups as well, in which case Kigyo's answer is probably the right one.

One of the nice things about functional programming is that it can often free you from working with indices, though, so for the sake of completeness, here's an implementation using span that doesn't need to track the indices of groups (first for the simple form without element indices):

val numbers = Seq(5, 3, 4, 1)

numbers.foldLeft(List.empty[List[Int]]) {
  case (acc, x) => acc.span(_.exists(y => math.abs(x - y) > 2)) match {
    case (bad, picked :: rest) => (x :: picked) :: rest ::: bad
    case (bad, _) => List(x) :: bad
  }
}

If you haven't already zipWithIndex-ed numbers, you can also take care of that during the fold without too much extra fuss:

val numbers = Seq(5, 3, 4, 1)

numbers.foldLeft(List.empty[List[(Int, Int)]], 0) {
  case ((acc, i), x) => acc.span(_.exists(y => math.abs(x - y._1) > 2)) match {
    case (bad, picked :: rest) => (((x, i) :: picked) :: rest ::: bad, i + 1)
    case (bad, _) => (List((x, i)) :: bad, i + 1)
  }
}._1

This returns List(List((1, 3)), List((4, 2), (3, 1), (5, 0))) as expected, and saves you an iteration through the sequence with very little extra verbosity.


Need Your Help

How to pass a Drawable into a class?

java android android-drawable

Is there anyway to pass a Drawable through a class like so:

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.