Как преобразовать список в список списков по группам элементов, когда элемент повторяется в Scala идиоматическим способом - PullRequest
Новая
       7

Как преобразовать список в список списков по группам элементов, когда элемент повторяется в Scala идиоматическим способом

0 голосов
/ 27 октября 2018

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

Введите: 

List(1, 2, 3, 1, 2, 1, 3, 1, 2, 3)

Ouput: 

List[List[Integer]] = List(List(1, 2, 3), List(1, 2), List(1, 3), List(1, 2, 3))

Вот что я пробовал: 

val tokens = List(1,2,3,1,2,1,3,1,2,3)

val group = new ListBuffer[List[Integer]]()
val nextGroup = new ListBuffer[Integer]()
val nextTokens = new ListBuffer[Integer]()

for (t <- tokens) {
  if (nextTokens.contains(t)) {
    group += nextGroup.toList
    nextGroup.clear()
    nextTokens.clear()
  }
  nextGroup += t
  nextTokens += t
}

group += nextGroup.toList

group.toList

Я ищу лучший способ добиться этого, используя функции map / foldLeft ... без использования ListBuffer.

Заранее спасибо.

Ответы [ 3 ]

0 голосов
/ 27 октября 2018

Используя решение, представленное ниже для вопроса, я предложил следующее решение

https://stackoverflow.com/a/52976957/1696418

mySeq.foldLeft(List.empty[List[Int]]) {
  case (acc, i) if acc.isEmpty => List(List(i))
  case (acc, i) if acc.last.contains(i) => acc :+ List(i)
  case (acc, i) => acc.init :+ (acc.last :+ i)
}
0 голосов
/ 27 октября 2018

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

val (acc, last) = tokens.foldLeft ((List[List[Int]](), List[Int]())) ((a,b) =>
            if (a._2.contains(b)) (a._1 :+ a._2, List(b))
            else (a._1, a._2 :+ b))
acc :+ last

Обратите внимание, что это не самое эффективное в вычислительном отношении решение, поскольку для каждой итерации мы проверяем весь рассматриваемый подсписок, используя contains.Если вы хотите повысить эффективность, вы можете (в зависимости от ваших данных) рассмотреть подход, в котором вместо быстрых проверок повторений используются хеш-карты или аналогичные структуры данных.

0 голосов
/ 27 октября 2018

Вот версия, использующая foldLeft

tokens
  .drop(1)
  .foldLeft(List(tokens.take(1))) { case (res, token) =>
    if (res.head.contains(token)) {
      List(token) +: res
    } else {
      (res.head :+ token) +: res.tail
    }
  }
  .reverse

Использование drop и take гарантирует, что это работает в пустом списке. Построение результата в обратном порядке означает, что последний List всегда стоит во главе, а также будет эффективен для длинных списков.

А для полноты вот рекурсивная функция, которая делает то же самое: 

def groupDistinct[T](tokens: List[T]): List[List[T]] = {
  @tailrec
  def loop(token: List[T], cur: List[T], res: List[List[T]]): List[List[T]] =
    token match {
      case Nil =>
        res :+ cur
      case head :: tail =>
        if (cur.contains(head)) {
          loop(tail, List(head), res :+ cur)
        } else {
          loop(tail, cur :+ head, res)
        }
    }

  loop(tokens, Nil, Nil)
}
...