CODEWITHSUNDEEP
scala
Long Thai
Long Thai

Reputation: 817

Group list of numbers into groups based on the range from the lowest number

Assuming there the list of numbers and a range value, I want to group them into groups, in which the item in each group is within the range from the lowest number, and sort them.

For example, I have a list val l = List(1,2,3,4,5,6,7,8,9,10) and the range val range = 2. Then, I'm looking for a way to output the following result: result = List(List(1,2,3), List(4,5,6), List(7,8,9), List(10)). Which means if range = 0 then only identical numbers are in the same group.

At the moment, I use the following method

val minVal = l.min
val range1 = (minVal + range).toDouble
val groups = l.foldLeft(Map[Int, List[Int]]())((result, num) => {
    val numRange = math.ceil(num / range1).toInt
    if (result.contains(numRange)) {
        result.updated(numRange, num :: result(numRange))
    } else {
        result.updated(numRange, List(num))
    }
})
groups.keys.toList.sortBy(k => k).map(groups(_))

It works in most cases except when range = 0 and slowestNum != 1. E.g. for the list val l = List(2,3,4,5,6,7,8,9,10) and the range val range = 2, the result is List(List(2), List(4, 3), List(6, 5), List(8, 7), List(10, 9)).

So, I wonder if there is any other way to solve this problem.

Upvotes: 4

Views: 1659

Answers (3)

Rok Kralj
Rok Kralj

Reputation: 48755

Why complicate?

def coll(l: List[Int], range: Int): List[List[Int]] =
    if (l.isEmpty) Nil else {
        val (b, a) = l.span((l.head - range to l.head + range).contains)
        b :: coll(a, range)
    }

So, this algorithm collects numbers into a group until the number are in the plus/minus range.

val list = List(7,4,1,9,10,20,50,52,30)
coll(list, 3)
res6: List[List[Int]] = List(List(7, 4), List(1), List(9, 10), List(20), List(50, 52), List(30))

If you want each group by itself sorted, then call res6.map(_.sorted).

Upvotes: 6

mohit
mohit

Reputation: 4999

Try something like this 

val groupedList = l.map(i => l.filter(s => s >= i && s - i <= range))

groupedList.foldLeft(List(groupedList.head)) {
      case (r, c) => if (r.last.last < c.head) r ++ List(c) else r
 }

For range 2 

val l = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
val range = 2                                   
val groupedList = l.map(i => l.filter(s => s >= i && s - i <= range))
groupedList.foldLeft(List(groupedList.head)) {
case (r, c) => if (r.last.last < c.head) r ++ List(c) else r
}                                               
//> res0: List[List[Int]] = List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9), List(10))

For range 0

 val l = List(1,1,1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
 val range = 0                                  
val groupedList = l.map(i => l.filter(s => s >= i && s - i <= range))
groupedList.foldLeft(List(groupedList.head)) {
case (r, c) => if (r.last.last < c.head) r ++ List(c) else r
}                                              
 //> res0: List[List[Int]] = List(List(1, 1, 1), List(2), List(3), List(4), List(5), List(6), List(7), List(8), List(9), List(10))

Upvotes: 1

ale64bit
ale64bit

Reputation: 6242

I would personally do something like this:

val l = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
val range = 2

val result = l.sorted.foldLeft(List[List[Int]]()) {
  (cur, x) =>
    if ((cur nonEmpty) && x - cur.head.last <= range) (x :: cur.head) :: cur.tail
    else List(x) :: cur
}

although there may be some clever and neat ways. Of course, you can always do if you want the result ordered:

val ret = result.reverse.map(_.reverse)

Hope it helped!

Upvotes: 3

Related Questions