CODEWITHSUNDEEP
scala
Allen Wang
Allen Wang

Reputation: 2502

double for loop in scala with incrementing inner index

I'm trying to create a simple function to find the two closest pairs in a list. Since this operation involves comparing TWO elements in the list, I am not sure using a for loop works if it really is just sugar for map and flatmap. So far, I have the structure of the expression as this:

val points: List[(Double, Double)] = List((2.0,3.1),(3.5,2.3),(1.2,0.2),(6.4,2.4))
var minDistance = Double.PositiveInfinity
var closestPoints = ((Double.NaN, Double.NaN), (Double.NaN, Double.NaN))

for {
  point1 <- points
  point2 <- points if (point1 != point2) 
  if (distance(point1, point2) < minDistance): {
    minDistance = distance(point1, point2)
    closestPoints = (point1, point2)
  }
} yield (I guess I don't want a yield here?)

Note that the if (point1 != point2) is not really what I want here, since I really want to compare distinct points in the list, even if they have the same value. Would this only be possible using something like

for {
  index1 <- 0 until points.length
  index2 <- 0 until index1
...

This still seems unsatisfactory because of the yield? I guess there is some foldleft implementation that works, but I also don't know how to iterate on smaller and smaller subsets in the inner loop. I find foldLeft to be confusing to reason about compared to a simple double loop.

Upvotes: 2

Views: 212

Answers (2)

Yuval Itzchakov
Yuval Itzchakov

Reputation: 149518

You can achieve this using combinations and foldLeft:

points
  .combinations(2)
  .foldLeft((Double.PositiveInfinity,
    ((Double.NaN, Double.NaN), (Double.NaN, Double.NaN)))) { 
    case (acc, List(firstPoint, secondPoint)) =>
      val dist = distance(firstPoint, secondPoint)
      if (dist < acc._1) (dist, (firstPoint, secondPoint)) else acc
  }

If you only care about the points, and not the actual distance between them, minBy can be less verbose:

points
  .combinations(2)
  .minBy { case List(first, second) => distance(first, second) }

Upvotes: 3

zhang rui
zhang rui

Reputation: 81

for{
    point1, i <- points.view.zipWithIndex
    point2, j <- points.view.zipWithIndex if( i > j)
    #add whatever you want to do next
}

But I would say 

points.combinations(2).minBy{ pair => distance(pair(0), pair(1)) }

works as well.

Upvotes: 1

Related Questions