Group List Elemente mit einem Abstand von weniger als x

Question

Ich versuche, eine Möglichkeit zu finden, alle Objekte in einer Liste abhängig von einem x Abstand zwischen den Elementen zu gruppieren.

Zum Beispiel, wenn eine Entfernung von 1 dann

List(2,3,1,6,10,7,11,12,14) 

geben würde

List(List(1,2,3), List(6,7), List(10,11,12), List(14)) 

ich nur mit kniffligen Ansätzen und Schleifen kommen kann, aber ich denke, es muss eine saubere Lösung.

Answer 1

Sie können versuchen, Ihre Liste zu sortieren und dann foldLeft darauf zu verwenden. Grundsätzlich so etwas

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 
     } 
    } 
    ) 
    } 

Das Ergebnis scheint in Ordnung, aber umgekehrt. Rufen Sie bei Bedarf "reverse" auf den Listen auf. der Code wird

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 

Answer 2

Die sauberste Antwort auf eine Methode verlassen würde, die wahrscheinlich groupedWhile aufgerufen werden soll, die genau würde spalten, wo eine Bedingung wahr war. Wenn Sie diese Methode hatte, dann wäre es nur

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

sein, aber wir haben nicht groupedWhile.

Also lassen Sie uns machen:

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) 
} 

Nun, da Sie die generische Fähigkeit haben, können Sie die spezifischen leicht.