Считать последовательные символы в списке?

Question

Я хочу создать метод scala, который подсчитывает количество последовательных символов, значения которых совпадают.Итак, у меня есть этот список:

List ('a', 'a', 'b')

, и я хочу вернуть что-то вроде List (('a', 2), 'b ', 1) - потому что рядом находятся два символа с одинаковыми значениями.У меня был удар на этом с небольшим успехом:

  def recursivelyCompressList(list: List[(Char, Int)], newString: List[(Char, Int)]): List[(Char, Int)] = {

    list match {
      case Nil => newString
      case s :: tail => {
        if (tail.nonEmpty && s._1 == tail.head._1) {
          recursivelyCompressList(tail, newString :+ (s._1, s._2 + 1))
        } else {
          recursivelyCompressList(tail, newString :+ s)
        }

      }
      case _ => newString

    }

  }

Благодарен за любое руководство.

Answer 1

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

def comp(xs:List[Char]):List[(Char,Int)] =
    if(xs.isEmpty) Nil
    else {
      val h = xs.head
      val (m,r) = xs.span(_ == h)
      (h, m.length) :: comp(r)
    }

Answer 2

Просто foldRight() над вашей коллекцией (строка, список, массив, что угодно).

"aabaxxx".foldRight(List.empty[(Char,Int)]){
  case (c, Nil) => List((c,1))
  case (c, hd::tl) if c == hd._1 => (c, hd._2 + 1) :: tl
  case (c, lst) => (c,1) :: lst
}
//res0: List[(Char, Int)] = List((a,2), (b,1), (a,1), (x,3))

Answer 3

Использование takeWhile и dropWhile

Количество последовательных

def count(xs: List[Char]): List[(Char, Int)] =
if (xs.isEmpty) Nil else
 (xs.head, xs.takeWhile(_ == xs.head).length) :: count(xs.dropWhile(_ == xs.head))

Scala REPL

scala> def count(xs: List[Char]): List[(Char, Int)] =
     | if (xs.isEmpty) Nil else
     |  (xs.head, xs.takeWhile(_ == xs.head).length) :: count(xs.dropWhile(_ == xs.head))
count: (xs: List[Char])List[(Char, Int)]

scala> count(List('a', 'a', 'b', 'c', 'c', 'c'))
res0: List[(Char, Int)] = List((a,2), (b,1), (c,3))

scala> count(List('a', 'a', 'b', 'a', 'c', 'c', 'c'))
res1: List[(Char, Int)] = List((a,2), (b,1), (a,1), (c,3))

Answer 4

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

def rec(list : List[Char]) : Map[Char, Int] = {

  @scala.annotation.tailrec
  def helper(prev: Char, li : List[Char], len : Int, result : Map[Char, Int]) : Map[Char,Int] = {
    if(li.isEmpty) {
      if(!result.contains(prev)) result + (prev -> len)
      else if(result(prev) < len) result + (prev -> len)
      else result
    }
    else {
      val cur = li.head
      if(cur != prev) {
        if(result.contains(prev)) {
          if(result(prev) < len)
            helper(li.head, li.tail, 1, result + (prev -> len))
          else
            helper(li.head, li.tail, 1, result)
        } else {
          helper(li.head, li.tail, 1, result + (prev -> len))
        }
      } else {
        helper(li.head, li.tail, len + 1, result)
      }
    }
  }
  helper('\0', list, 0, Map.empty[Char, Int]) - '\0'
}

Запуск

rec(List('c', 'a', 'a', 'a', 'c', 'd' ,'c', 'c' , 'a', 'a', 'd', 'd', 'd', 'd','c','c','a', 'c','c','c'))

Вывод:

res0: Map[Char,Int] = Map(c -> 3, a -> 3, d -> 4)

Идея состоит в том, чтобы просто посмотреть на текущий символ в списке и предыдущий символ.Когда символ изменяется, счетчик последовательности останавливается и текущая длина сравнивается с тем, что хранится на карте.Это довольно просто, если подумать.

Я думаю, что это можно написать более элегантно.Но это может быть хорошей отправной точкой.

Answer 5

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

def compressList[T](list: List[T]): List[(T, Int)] = {
  @annotation.tailrec
  def loop(remaining: List[T], currentValue: T, currentCount: Int, acc: List[(T, Int)]): List[(T, Int)] =
    remaining match {
      case Nil =>
        ((currentValue -> currentCount) :: acc).reverse

      case t :: tail =>
        if (t == currentValue)
          loop(
            remaining = tail,
            currentValue,
            currentCount + 1,
            acc
          )
        else
          loop(
            remaining = tail,
            currentValue = t,
            currentCount = 1,
            (currentValue -> currentCount) :: acc
          )
    }

  list match {
    case Nil =>
      Nil

    case t :: tail =>
      loop(
        remaining = tail,
        currentValue = t,
        currentCount = 1,
        acc = List.empty
      )
  }
}

Что вы можете использовать следующим образом:

compressList(List.empty[Char])
// res: List[(Char, Int)] = List()

compressList(List('a', 'b'))
// res: List[(Char, Int)] = List(('a', 1), ('b', 1))

compressList(List('a', 'a', 'b'))
// res: List[(Char, Int)] = List(('a', 2), ('b', 1))

compressList(List('a', 'a', 'b', 'b', 'b', 'a', 'c'))
// res: List[(Char, Int)] = List(('a', 2), ('b', 3), ('a', 1), ('c', 1))