Разбиение строки на группы

Question

Я пытаюсь 'сгруппировать' строку в сегменты, я думаю, этот пример объяснит это более кратко

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

Я могу предложить несколько способов сделать это в императивном стиле (с помощьюvars и пошагово перебирая строку, чтобы найти группы), но мне было интересно, можно ли найти какое-нибудь лучшее функциональное решение?Я просматривал Scala API, но, похоже, что-то, что соответствует моим потребностям.

Любая помощь будет признательна

Answer 1

Вы можете разделить строку рекурсивно с помощью span:

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

Хвост рекурсивный:

@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

Кажется, что все остальные ответы очень сосредоточены на операциях по сбору.Но решение для чистой строки и регулярных выражений намного проще:

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

В этом регулярном выражении я использую положительный взгляд назад и отрицательный взгляд для захваченного символа

Answer 3

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

---

Редактировать: Хвостовая рекурсивная версия:

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

может использоваться так же, как и другой, поскольку второй параметр имеет значение по умолчанию и, следовательно, не долженбыть поставленным.

Answer 4

Сделать это одним вкладышем:

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)

UPDATE

Как упоминал @Paul о заказе, здесь обновленная версия:

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

Answer 5

Функциональное * решение с использованием 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
    }
  }
}

За все эти операции с последовательностями, выполняемыми над строками, скрывается большая стоимость (через неявное преобразование). Я предполагаю, что реальная сложность сильно зависит от типа Seq строк, которые преобразуются в.

(*) Afaik все / большинство операций в библиотеке коллекции зависят от итераторов, что, по сути, является не функциональной концепцией. Но код выглядит функциональным, по крайней мере.

Answer 6

Вы можете использовать некоторые вспомогательные функции, такие как:

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)

Это должно сработать, верно?Без сомнения, он может быть очищен в один слой еще дальше

Answer 7

Если вы хотите использовать scala API, вы можете использовать встроенную функцию для этого:

str.groupBy(c => c).values

Или, если вы не возражаете, это будет отсортировано и в списке:

str.groupBy(c => c).values.toList.sorted

Answer 8

Начиная с Scala 2.13, List теперь поставляется с компоновщиком unfold, который можно комбинировать с String::span:

List.unfold("aaaabbaaacdeeffg") {
  case ""   => None
  case rest => Some(rest.span(_ == rest.head))
}
// List[String] = List("aaaa", "bb", "aaa", "c", "d", "ee", "ff", "g")

или, в качестве альтернативы, в сочетании с Scala 2.13 Option#unless строитель:

List.unfold("aaaabbaaacdeeffg") {
  rest => Option.unless(rest.isEmpty)(rest.span(_ == rest.head))
}
// List[String] = List("aaaa", "bb", "aaa", "c", "d", "ee", "ff", "g")

---

подробности:

• Развернуть (def unfold[A, S](init: S)(f: (S) ⇒ Option[(A, S)]): List[A]) основано на внутреннем состоянии (init), которое в нашем случае инициализируется с "aaaabbaaacdeeffg".
• Для каждой итерации мы span (def span(p: (Char) ⇒ Boolean): (String, String)) это внутреннее состояние, чтобы найти префикс, содержащий тот же символ, и создать кортеж (String, String), который содержит префикс и остальную часть строки. span очень удачно в этом контексте, поскольку он производит именно то, что ожидает unfold: кортеж, содержащий следующий элемент списка и новое внутреннее состояние.
• Развертывание прекращается, когда внутреннее состояние равно "", и в этом случае мы производим None, как и ожидалось при развертывании для выхода.

Answer 9

Редактировать: Надо читать более внимательно. Ниже нет функционального кода.

Иногда немного изменяемое состояние помогает:

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
}

Время выполнения O (n) (если сегменты имеют максимально постоянную длину), а tmp.+=, вероятно, создает наибольшую нагрузку. Вместо этого используйте строковый конструктор для строгой среды выполнения в O (n).

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