Elementi elenco di gruppi con una distanza inferiore a x

Question

Sto cercando di trovare un modo per raggruppare tutti gli oggetti in un elenco a seconda della distanza x tra gli elementi.

Per esempio, se la distanza è 1 poi

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

darebbe

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

posso venire solo con approcci difficili e loop, ma credo che ci deve essere una soluzione più pulita.

Answer 1

Si può provare a ordinare l'elenco e quindi utilizzare un foldLeft su di esso. Fondamentalmente qualcosa del genere

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

Il risultato sembra essere ok ma invertito. Chiamare "reverse" se necessario, quando necessario, negli elenchi. il codice diventa

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

La risposta più pulita sarebbe contare su un metodo che probabilmente dovrebbe essere chiamato groupedWhile che avrebbe diviso esattamente dove una condizione era vero. Se tu avessi questo metodo, allora sarebbe solo

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

Ma non abbiamo groupedWhile.

Quindi cerchiamo di fare uno:

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

Ora che avete la capacità generica, è possibile ottenere quello specifico facilmente.