如何旋转(循环移位)Scala集合

Question

我可以很容易地,干净利落地使用for循环.例如,如果我想Seq从每个元素遍历到自身,我会执行以下操作:

val seq = Seq(1,2,3,4,5)

for (i <- seq.indices) {
    for (j <- seq.indices) {
        print(seq(i + j % seq.length))
    }
}

但是当我正在寻找fold这个系列时,我想知道是否有更惯用的方法.递归方法可以让我避免任何vars.但基本上,我想知道以下是否可能:

seq.rotatedView(i)

这将创建旋转视图,如旋转位(或循环移位).

Answer 1

如下所示:

scala> def rotatedView(i:Int)=Seq(1,2,3,4,5).drop(i)++Seq(1,2,3,4,5).take(i)
rotatedView: (i: Int)Seq[Int]

scala> rotatedView(1)
res48: Seq[Int] = List(2, 3, 4, 5, 1)

scala> rotatedView(2)
res49: Seq[Int] = List(3, 4, 5, 1, 2)

Answer 2

这应该以相当通用的方式进行,并允许任意旋转:

def rotateLeft[A](seq: Seq[A], i: Int): Seq[A] = {
    val size = seq.size
    seq.drop(i % size) ++ seq.take(i % size)
}

def rotateRight[A](seq: Seq[A], i: Int): Seq[A] = {
    val size = seq.size
    seq.drop(size - (i % size)) ++ seq.take(size - (i % size))
}

这个想法很简单,向左旋转,左边drop的第一个i元素,take再从左边旋转,以相反的顺序连接它们.如果您不介意计算集合的大小,您可以以大小为模的操作,以允许i任意.

scala> rotateRight(seq, 1)
res34: Seq[Int] = List(5, 1, 2, 3, 4)

scala> rotateRight(seq, 7)
res35: Seq[Int] = List(4, 5, 1, 2, 3)

scala> rotateRight(seq, 70)
res36: Seq[Int] = List(1, 2, 3, 4, 5)

同样,您可以使用splitAt:

def rotateLeft[A](seq: Seq[A], i: Int): Seq[A] = {
    val size = seq.size
    val (first, last) = seq.splitAt(i % size)
    last ++ first
}

def rotateRight[A](seq: Seq[A], i: Int): Seq[A] = {
    val size = seq.size
    val (first, last) = seq.splitAt(size - (i % size))
    last ++ first
}

为了使它更通用,使用丰富我的库模式:

import scala.collection.TraversableLike
import scala.collection.generic.CanBuildFrom

implicit class TraversableExt[A, Repr <: TraversableLike[A, Repr]](xs: TraversableLike[A, Repr]) {

    def rotateLeft(i: Int)(implicit cbf: CanBuildFrom[Repr, A, Repr]): Repr = {
        val size = xs.size
        val (first, last) = xs.splitAt(i % size)
        last ++ first
    }

    def rotateRight(i: Int)(implicit cbf: CanBuildFrom[Repr, A, Repr]): Repr = {
        val size = xs.size
        val (first, last) = xs.splitAt(size - (i % size))
        last ++ first
    }

}

scala> Seq(1, 2, 3, 4, 5).rotateRight(2)
res0: Seq[Int] = List(4, 5, 1, 2, 3)

scala> List(1, 2, 3, 4, 5).rotateLeft(2)
res1: List[Int] = List(3, 4, 5, 1, 2)

scala> Stream(1, 2, 3, 4, 5).rotateRight(1)
res2: scala.collection.immutable.Stream[Int] = Stream(5, ?)

请记住,这些并不一定是性能最佳的,它们也无法使用无限集合(没有人可以).

Answer 3

根据OP的评论,他们想要折叠它,这里有一个略微不同的看法,避免先计算序列的长度.

定义将迭代旋转序列的迭代器

class RotatedIterator[A](seq: Seq[A], start: Int) extends Iterator[A] {
  var (before, after) = seq.splitAt(start)
  def next = after match {
    case Seq()  =>
      val (h :: t) = before; before = t; h
    case h :: t => after = t; h
  }
  def hasNext = after.nonEmpty || before.nonEmpty
}

并像这样使用它:

val seq = List(1, 2, 3, 4, 5)  
val xs = new RotatedIterator(seq, 2)
println(xs.toList)         //> List(3, 4, 5, 1, 2)