Group by margin

Question

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?

Answer 1

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