scala - 组合多个任意长度的列表

Question

我正在寻找一种以下列方式加入多个列表的方法：

ListA a b c
ListB 1 2 3 4
ListC + # * § %
..
..
..

Resulting List: a 1 + b 2 # c 3 * 4 § %

In Words：按顺序排列的元素，从第一个列表开始组合到结果列表中。任意数量的输入列表的长度可能不同。

我使用了多种 zip 变体、滑动迭代器的方法，但都没有奏效，尤其是处理了不同的列表长度。scala 中必须有一种优雅的方式；）

Answer 1

val lists = List(ListA, ListB, ListC)

lists.flatMap(_.zipWithIndex).sortBy(_._2).map(_._1)

这是不言自明的。它只是压缩每个值及其在其各自列表中的位置，按索引排序，然后将值拉回。

Answer 2

这是我的做法：

class ListTests extends FunSuite {
  test("The three lists from his example") {
    val l1 = List("a", "b", "c")
    val l2 = List(1, 2, 3, 4)
    val l3 = List("+", "#", "*", "§", "%")

    // All lists together
    val l = List(l1, l2, l3)

    // Max length of a list (to pad the shorter ones)
    val maxLen = l.map(_.size).max

    // Wrap the elements in Option and pad with None
    val padded = l.map { list => list.map(Some(_)) ++ Stream.continually(None).take(maxLen - list.size) }

    // Transpose 
    val trans = padded.transpose

    // Flatten the lists then flatten the options
    val result = trans.flatten.flatten

    // Viola 
    assert(List("a", 1, "+", "b", 2, "#", "c", 3, "*", 4, "§", "%") === result)
  }
}

Answer 3

这是一个小的递归解决方案。

def flatList(lists: List[List[Any]]) = {
  def loop(output: List[Any], xss: List[List[Any]]): List[Any] = (xss collect { case x :: xs => x }) match {
    case Nil => output
    case heads => loop(output ::: heads, xss.collect({ case x :: xs => xs })) 
  }
  loop(List[Any](), lists)
}

这是一种简单的流方法，可以处理任意序列的序列，每个序列可能无限长。

def flatSeqs[A](ssa: Seq[Seq[A]]): Stream[A] = {
  def seqs(xss: Seq[Seq[A]]): Stream[Seq[A]] = xss collect { case xs if !xs.isEmpty => xs } match {
    case Nil => Stream.empty
    case heads => heads #:: seqs(xss collect { case xs if !xs.isEmpty => xs.tail })
  }
  seqs(ssa).flatten
}

Answer 4

如果效率至关重要，这是一个必要的解决方案：

def combine[T](xss: List[List[T]]): List[T] = {
  val b = List.newBuilder[T]
  var its = xss.map(_.iterator)
  while (!its.isEmpty) {
    its = its.filter(_.hasNext)
    its.foreach(b += _.next)
  }
  b.result
}

Answer 5

您可以在此处使用padTo,transpose和flatten以取得良好效果：

lists.map(_.map(Some(_)).padTo(lists.map(_.length).max, None)).transpose.flatten.flatten

Answer 6

这里有一些简短但不是非常有效的东西：

def heads[A](xss: List[List[A]]) = xss.map(_.splitAt(1)).unzip
def interleave[A](xss: List[List[A]]) = Iterator.
  iterate(heads(xss)){ case (_, tails) => heads(tails) }.
  map(_._1.flatten).
  takeWhile(! _.isEmpty).
  flatten.toList

Answer 7

这是一个 O(n) 的递归解决方案。接受的解决方案（使用排序）是 O(nlog(n))。我所做的一些测试表明，由于转置的实现，使用转置的第二种解决方案也是O(nlog(n))。下面使用 reverse 看起来很可疑（因为它本身就是一个 O(n) 操作），但要说服自己它要么不能被太频繁地调用，要么不能在太大的列表中调用。

def intercalate[T](lists: List[List[T]]) : List[T] = {
    def intercalateHelper(newLists: List[List[T]], oldLists: List[List[T]], merged: List[T]): List[T] = {
      (newLists, oldLists) match {
        case (Nil, Nil) => merged
        case (Nil, zss) => intercalateHelper(zss.reverse, Nil, merged)
        case (Nil::xss, zss) => intercalateHelper(xss, zss, merged)
        case ( (y::ys)::xss, zss) => intercalateHelper(xss, ys::zss, y::merged)
      }
    }
    intercalateHelper(lists, List.empty, List.empty).reverse
  }