How do you rotate (circular shift) of a Scala coll

问题:

I can do this quite easily, and cleanly, using a for loop. For instance, if I wanted to traverse a Seq from every element back to itself I would do the following:

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

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

But as I'm looking to fold over the collection, I'm wondering if there is a more idiomatic approach. A recursive approach would allow me to avoid any vars. But basically, I'm wondering if something like the following is possible:

seq.rotatedView(i)

Which would create a rotated view, like rotating bits (or circular shift).

回答1:

Following the OP's comment that they want to fold over it, here's a slightly different take on it that avoids calculating the length of the sequence first.

Define an iterator that will iterate over the rotated sequence

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
}

And use it like this:

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

回答2:

Is it like below:

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)

回答3:

This ought to do it in a fairly generic way, and allow for arbitrary rotations:

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))
}

The idea is simple enough, to rotate left, drop the first i elements from the left, and take them again from the left to concatenate them in the opposite order. If you don't mind calculating the size of the collection, you can do your operations modulo the size, to allow i to be arbitrary.

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)

Similarly, you can use 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
}

---

To make it even more generic, using the enrich my library pattern:

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, ?)

---

Keep in mind these are not all necessarily the most tuned for performance, and they also can't work with infinite collections (none can).

回答4:

Given:

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

Solution:

seq.zipWithIndex.groupBy(_._2<3).values.flatMap(_.map(_._1))

or

seq.zipWithIndex.groupBy(_._2<3).values.flatten.map(_._1)

Result:

List(4, 5, 1, 2, 3)

1. If rotation is more than length of collection - we need to use rotation%length, if negative than formula (rotation+1)%length and take absolute value.
2. It's not efficient

回答5:

Here is one liner solution

def rotateRight(A: Array[Int], K: Int): Array[Int] = {
    if (null == A || A.size == 0) A else (A drop A.size - (K % A.size)) ++ (A take A.size - (K % A.size))
}
rotateRight(Array(1,2,3,4,5), 3)

回答6:

Here's a fairly simple and idiomatic Scala collections way to write it:

def rotateSeq[A](seq: Seq[A], isLeft: Boolean = false, count: Int = 1): Seq[A] =
  if (isLeft)
    seq.drop(count) ++ seq.take(count)
  else
    seq.takeRight(count) ++ seq.dropRight(count)

回答7:

We can simply use foldLeft to reverse a list as below.

  val input = List(1,2,3,4,5)

  val res = input.foldLeft(List[Int]())((s, a) => { List(a) ++: s})

  println(res) // List(5, 4, 3, 2, 1)

回答8:

Another tail-recursive approach. When I benchmarked it with JMH it was about 2 times faster than solution based on drop/take:

def rotate[A](list: List[A], by: Int): List[A] = {

    @tailrec
    def go(list: List[A], n: Int, acc: List[A]): List[A] = {

      if(n > 0) {
        list match {
          case x :: xs => go(xs, n-1, x :: acc)
        }
      } else {
        list ++ acc.reverse
      }

    }

    if (by < 0) {
      go(list, -by % list.length, Nil)
    } else {
      go(list, list.length - by % list.length, Nil)
    }    
}

//rotate right
rotate(List(1,2,3,4,5,6,7,8,9,10), 3) // List(8, 9, 10, 1, 2, 3, 4, 5, 6, 7) 

//use negative number to rotate left
rotate(List(1,2,3,4,5,6,7,8,9,10), -3) // List(4, 5, 6, 7, 8, 9, 10, 1, 2, 3)