cadena de la división en grupos

Question

que estoy tratando de 'grupo' una cadena en segmentos, supongo que este ejemplo lo explicaría más sucintamente

scala> val str: String = "aaaabbcddeeeeeeffg" 
... (do something) 
res0: List("aaaa","bb","c","dd","eeeee","ff","g") 

puedo thnk de algunas maneras de hacer esto en un estilo imperativo (con vars y pasando por la cadena para encontrar grupos) pero me preguntaba si se podría lograr alguna solución funcional mejor ? He estado buscando a través de la API de Scala, pero no parece haber algo que se ajuste a mis necesidades.

Cualquier ayuda se agradece

Answer 1

Puede dividir la cadena de forma recursiva con el palmo:

def s(x : String) : List[String] = if(x.size == 0) Nil else { 
    val (l,r) = x.span(_ == x(0)) 
    l :: s(r) 
} 

cola recursiva:

@annotation.tailrec def s(x : String, y : List[String] = Nil) : List[String] = { 
    if(x.size == 0) y.reverse 
    else { 
     val (l,r) = x.span(_ == x(0)) 
     s(r, l :: y) 
    } 
} 

Answer 2

def group(s: String): List[String] = s match { 
    case "" => Nil 
    case s => s.takeWhile(_==s.head) :: group(s.dropWhile(_==s.head)) 
} 

---

Edición: cola versión recursiva:

def group(s: String, result: List[String] = Nil): List[String] = s match { 
    case "" => result reverse 
    case s => group(s.dropWhile(_==s.head), s.takeWhile(_==s.head) :: result) 
} 

puede ser utilizado como el otro debido a que el segundo parámetro tiene un valor predeterminado y por lo tanto no tiene que ser suministrado.

Answer 3

Se podía utilizar algunas funciones auxiliares como esto:

val str = "aaaabbcddddeeeeefff" 

def zame(chars:List[Char]) = chars.partition(_==chars.head) 

def q(chars:List[Char]):List[List[Char]] = chars match { 
    case Nil => Nil 
    case rest => 
     val (thesame,others) = zame(rest) 
     thesame :: q(others) 
} 

q(str.toList) map (_.mkString) 

Esto debe hacer el truco, ¿verdad? No hay duda de que se puede limpiar en una sola línea aún más

Answer 4

Que sea de una sola línea:

scala> val str = "aaaabbcddddeeeeefff" 
str: java.lang.String = aaaabbcddddeeeeefff 

scala> str.groupBy(identity).map(_._2) 
res: scala.collection.immutable.Iterable[String] = List(eeeee, fff, aaaa, bb, c, dddd) 

ACTUALIZACIÓN:

Como se mencionó @ Pablo sobre el orden que aquí se actualiza la versión:

scala> str.groupBy(identity).toList.sortBy(_._1).map(_._2) 
res: List[String] = List(aaaa, bb, c, dddd, eeeee, fff) 

Answer 5

Editar: tiene que leer con más cuidado. A continuación no hay un código funcional.

A veces, un poco de estado mutable ayuda a:

def group(s : String) = { 
    var tmp = "" 
    val b = Seq.newBuilder[String] 

    s.foreach { c => 
    if (tmp != "" && tmp.head != c) { 
     b += tmp 
     tmp = "" 
    } 

    tmp += c 
    } 
    b += tmp 

    b.result 
} 

Runtime O (n) probablemente (si los segmentos tienen como máximo constante de longitud) y tmp.+= crea la mayor parte de arriba. Utilice un generador de cadenas en lugar de estricto tiempo de ejecución en O (n).

group("aaaabbcddeeeeeeffg") 
> Seq[String] = List(aaaa, bb, c, dd, eeeeee, ff, g) 

Answer 6

Parece que todas las otras respuestas están muy concentradas en las operaciones de cobro.Pero pura cuerda + solución de expresiones regulares es mucho más simple:

str split """(?<=(\w))(?!\1)""" toList 

En esta expresión regular que utilizan de búsqueda hacia atrás positiva y búsqueda negativa hacia delante para el carbón capturado

Answer 7

A * solución funcional utilizando fold:

def group(s : String) : Seq[String] = { 
    s.tail.foldLeft(Seq(s.head.toString)) { case (carry, elem) => 
    if (carry.last(0) == elem) { 
     carry.init :+ (carry.last + elem) 
    } 
    else { 
     carry :+ elem.toString 
    } 
    } 
} 

Hay un gran costo oculto en todas las operaciones de secuencia realizadas en cadenas (a través de la conversión implícita). Supongo que la complejidad real depende en gran medida del tipo de Seq en que las cadenas se convierten.

(*) Todas las operaciones de Afaik en la biblioteca de colecciones dependen de iteradores, un concepto intrínsecamente no funcional. Pero el código parece funcional, al menos.