你如何撰寫一個函式來將輸入串列分成三個子串列？-有解無憂

撰寫一個函式將輸入串列分成三個子串列。第一個子串列包含索引滿足方程 i mod 3 = 1 的所有元素。第二個子串列包含索引滿足方程且 mod 3 = 2 的所有元素。第三個子串列是包含剩余的元素。必須保持元素的順序。將結果作為三個串列回傳。使用尾遞回和非尾遞回撰寫函式。

我的嘗試：我很困惑如何增加索引以便它可以通過串列，關于如何每次增加索引使其遞回的任何建議？

        def divide(list: List[Int]): (List[Int], List[Int], List[Int]) = {
          var index:Int =0
          def splitList(remaining: List[Int], firstSubList: List[Int], secondSubList: List[Int], thirdSubList: List[Int], index:Int): (List[Int], List[Int], List[Int]) = {
            if(remaining.isEmpty) {
              return (List[Int](), List[Int](), List[Int]())
            }

            val splitted = splitList(remaining.tail, firstSubList, secondSubList, thirdSubList, index)

            val firstList = if (index % 3 == 1) List() ::: splitted._1 else splitted._1
            val secondList = if (index % 3 == 2) List() ::: splitted._2 else splitted._2
            val thirdList = if((index% 3 != 1) && (index % 3 != 2)) List() ::: splitted._3 else splitted._3
            index  1
            (firstSubList ::: firstList, secondSubList ::: secondList, thirdSubList ::: thirdList)

          }

          splitList(list, List(), List(), List(), index 1)
        }

      println(divide(List(0,11,22,33)))

uj5u.com熱心網友回復：

稍微概括一下要求，這是一種使用簡單遞回函式來組合原始串列索引的方法Map：Listmodulo n

def splitList[T](list: List[T], n: Int): Map[Int, List[T]] = {
  @scala.annotation.tailrec
  def loop(zls: List[(T, Int)], lsMap: Map[Int, List[T]]): Map[Int, List[T]] =
    zls match {
      case Nil =>
        lsMap.map{ case (i, ls) => (i, ls.reverse) }
      case (x, i) :: rest =>
        val j = i % n
        loop(rest, lsMap   (j -> (x :: lsMap.getOrElse(j, Nil))))
    }
  loop(list.zipWithIndex, Map.empty[Int, List[T]])
}

splitList(List(0, 11, 22, 33, 44, 55, 66), 3)
// Map(0 -> List(0, 33, 66), 1 -> List(11, 44), 2 -> List(22, 55))

splitList(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'), 4)
// Map(0 -> List(a, e, i), 1 -> List(b, f), 2 -> List(c, g), 3 -> List(d, h))

uj5u.com熱心網友回復：

要在現實生活中做到這一點，只需用索引標記每個值，然后按該索引模 3 分組：

def divide[T](list: List[T]) = {
  val g = list.zipWithIndex.groupMap(_._2 % 3)(_._1)

  (g.getOrElse(1, Nil), g.getOrElse(2, Nil), g.getOrElse(0, Nil))  
}

如果您堅持使用遞回版本，它可能如下所示：

def divide[T](list: List[T]) = {
  def loop(rem: List[T]): (List[T], List[T], List[T]) =
    rem match {
      case a::b::c::tail =>
        val rem = loop(tail)
        (b  : rem._1, c  : rem._2, a  : rem._3)
      case a::b::Nil =>
        (List(b), Nil, List(a))
      case a::Nil =>
        (Nil, Nil, List(a))
      case Nil =>
        (Nil, Nil, Nil)
    }

  loop(list)
}

尾遞回看起來像這樣：

def divide[T](list: List[T]) = {
  @annotation.tailrec
  def loop(rem: List[T], res: (List[T], List[T], List[T])): (List[T], List[T], List[T]) =
  rem match {
    case a::b::c::tail =>
        loop(tail, (res._1 :  b, res._2 :  c, res._3 :  a))
    case a::b::Nil =>
        (res._1 :  b, res._2, res._3 :  a)
    case a::Nil =>
        (res._1, res._2, res._3 :  a)
    case Nil =>
        res
  }

  loop(list, (Nil, Nil, Nil))
}

如果你關心效率，這個版本會以其他順序構建串列，并在回傳結果時反轉它們。

uj5u.com熱心網友回復：

你的問題是你放index 1錯地方了。嘗試交換它：index 1在你有的地方加入電話index，然后index進入另一個電話。還要洗掉index 1中間的“獨立”陳述句，它無論如何都不會做任何事情。

這應該使您的代碼作業......但它仍然不是很好。它有幾個問題（除了它結構糟糕、不習慣、難以閱讀，這有點主觀）：

它不是尾遞回的，并且有效地在堆疊上創建了整個串列的另一個副本。當串列很長時，這可能會出現問題。
它連接（可能很長）串列。這是一個壞主意。List在 scala 中是一個單鏈表，你可以隨時使用它的頭部，但是要到達最后，你需要花費 O(N) 個周期，遍歷每個節點。因此，像foo:::bar迭代函式這樣的事情會立即使任何演算法（至少）成為二次的。

避免最后一個問題的通常“技巧”是預先添加元素以逐個輸出，然后最終反轉結果。第一個可以通過尾遞回來避免。在這種情況下，“非慣用”和“難以閱讀”的問題主要通過 usingmatch陳述句來解決：

    def split3(
      in: List[Int], 
      one: List[Int], 
      two: List[Int], 
      three: List[Int], 
      index: Int = 0
    } = (in, index % 3) match {
      case (Nil, _) => (one.reverse, two.reverse, three.reverse)
      case (head::tail, 1) => split3(tail, head::one, two, three, index 1) 
      case (head::tail, 2) => split3(tail, one, head::two, three, index 1)
      case (head::tail, _) => split3(tail, one, two, head::three, index 1)
    }

現在，這是一個很好的解決方案，盡管對我苛刻的眼睛來說有點重復......但是如果想要聰明并真正釋放 scala 標準庫的全部功能，忘記遞回，在這種情況下你并不真的需要它。

如果您知道串列中的元素數總是可以被 3 整除，您可以這樣做list.grouped(3).toSeq.transpose：將串列分成三組（每組將 index%3=0 作為第一個元素，index%3=1 作為第二個元素， index%3=2 作為第三個），然后transpose將 3 個串列的串列轉換為三個串列的串列，其中第一個包含所有第一個元素，第二個 - 所有秒等。（我知道，你想要它們以不同的順序排列，但這很簡單）。如果您無法理解我在說什么，只需嘗試在一些串列上運行它，然后查看結果。

這將是一個非常優雅的解決方案......如果它有效：/問題是，它只有在原始串列中有 3*n 個元素時才會這樣做。如果沒有，transpose如果它沒有像所有其他元素一樣的 3 個元素，則會在最后一個元素上失敗。我們可以修復它嗎？嗯……這就是聰明的地方。

   val (triplets, tails) = list.grouped(3).toSeq.partition(_.size == 3) 
   triplets 
     .transpose
     .padTo(3, Nil)
     .zip(tails.flatten.map(Seq(_)).padTo(3, Nil))
     .map { case (head, tail) => head    tail }

基本上，它與我上面描述的單線做同樣的事情（分成 3 個組并轉置），但是為最后一組元素少于三個的情況添加了特殊處理 - 它將它拆分并填充所需數量的空串列，然后將結果附加到轉置的三元組。

轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/530959.html

標籤：斯卡拉函数式编程

上一篇：Scala：添加一個隱式方法將案例類轉換為別名物件中的另一個案例類？

下一篇：sparkscala無法使用agg決議列