Wie man Bereiche von zusammenhängenden Inten effizient/elegant extrahiert?

Question

Lassen Sie uns mit einer Folge von ganzzahligen beginnen wie:

val seq = List(1,2,3,4,5,6,9,10,11,14,15,16,18) 

Ich möchte eine Folge von Paaren bekommen repräsentieren zusammenhängende Sätze, wie:

val ranges = List(1,6,9,11,14,16,18,18) 

Alternative Format Seq[(Int,Int)] auch akzeptabel ist:

Erläuterung: - Ganzzahlen im Bereich 1..6 und 11..16 sind in seq - integer 18 in seq ist, hat aber keine Nachfolger oder Vorgänger, so scheint es, als 18,18 in ranges

Man beachte, daß Einzelelement-Sequenzen sollten immer paarweise berichtet werden, wie beispielsweise in:

val seq = List(18, 19, 21) 

, die als Ergebnis geben sollte:

val ranges = List(18,19,21,21) 

Oder, wenn Sie bevorzugen Tuple2 Stil:

val ranges = List((18,19),(21,21)) 

Ich möchte eine Funktion haben ranges von seq abzuleiten; eine Lösung (von einem Kollegen zur Verfügung gestellt) ist:

def toRanges(a: Seq[Int]): Seq[Int] = { 
    val min = a.map(x => (x, a contains x - 1)).filter(!_._2).map(_._1) 
    val max = a.map(x => (x, a contains x + 1)).filter(!_._2).map(_._1) 
    return (min ++ max).sorted 
} 

Welche elegant ist, in der Tat, aber ich bin mir nicht sicher über die Effizienz, von contains aufgrund verwenden.

Kann jemand eine noch bessere Lösung in Bezug auf Effizienz oder Eleganz bieten?

Vielen Dank!

Answer 1

Wenn die Eingabe ist bestellt (oder Sie sind bereit, es zuerst zu sortieren), können Sie dies ziemlich präzise in einem einzigen Durchgang mit foldLeft tun (gut, zwei Pässe mit der reverse, aber das ist ein Artefakt der Arbeit mit Listen und könnte vermieden werden, wenn Sie bereit sind, eine gewisse Eleganz geben):

seq.foldLeft[List[(Int, Int)]](Nil) { 
    case ((a, b) :: rest, i) if i == b + 1 => (a, i) :: rest 
    case (acc, i) => (i, i) :: acc 
}.reverse 

die in diesem Fall uns folgendes ergibt:

res0: List[(Int, Int)] = List((1,6), (9,11), (14,16), (18,18)) 

Für jedes Element, das wir prüfen, ob es der Nachfolger des ist Ende der letzten Reihe wir a dded. Wenn dies der Fall ist, ersetzen wir das Ende in diesem Bereich. Wenn nicht, beginnen wir eine neue Reihe.

Answer 2

So etwas wie dies vielleicht:

(None +: seq.toStream.map(x => Some(x)) :+ None).sliding(2).flatMap { 
    case Seq(None, Some(b)) => List(b) 
    case Seq(Some(a), None) => List(a) 
    case Seq(Some(a), Some(b)) if b - a == 1 => Nil 
    case Seq(Some(a), Some(b)) => List(a,b) 
}.toList