你如何旋转(循环移位)Scala 集合
How do you rotate (circular shift) of a Scala collection
我可以 使用 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
浏览整个集合时,我想知道是否有更惯用的方法。递归方法可以让我避免任何 var
s。但基本上,我想知道是否可能出现以下情况:
seq.rotatedView(i)
这将创建旋转视图,如旋转位(或循环移位)。
是不是像下面这样:
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)
这应该以一种相当通用的方式进行,并允许任意旋转:
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, ?)
请记住,这些不一定都是性能最优化的,它们也不能用于无限集合(none 可以)。
根据 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)
这是一种衬里解决方案
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)
鉴于:
val seq = Seq(1,2,3,4,5)
解决方案:
seq.zipWithIndex.groupBy(_._2<3).values.flatMap(_.map(_._1))
或
seq.zipWithIndex.groupBy(_._2<3).values.flatten.map(_._1)
结果:
List(4, 5, 1, 2, 3)
- 如果旋转大于集合的长度 - 我们需要使用
rotation%length
,如果负数小于公式 (rotation+1)%length
并取绝对值。
- 效率不高
这是一种相当简单且惯用的 Scala 集合编写方式:
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)
我们可以简单地使用foldLeft
来反转列表,如下所示。
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)
另一种尾递归方法。当我用 JMH 对它进行基准测试时,它比基于 drop/take:
的解决方案快大约 2 倍
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)
这是一段简单的代码
object tesing_it extends App
{
val one = ArrayBuffer(1,2,3,4,5,6)
val i = 2 //the number of index you want to move
for(z<-0 to i){
val y = 0
var x = one += one(y)
x = x -= x(y)
println("for seq after process " +z +" " + x)
}
println(one)
}
结果:
for seq after process 0 ArrayBuffer(2, 3, 4, 5, 6, 1)
for seq after process 1 ArrayBuffer(3, 4, 5, 6, 1, 2)
for seq after process 2 ArrayBuffer(4, 5, 6, 1, 2, 3)
ArrayBuffer(4, 5, 6, 1, 2, 3)
如果您不需要验证 "offset" 的另一种解决方案:
def rotate[T](seq: Seq[T], offset: Int): Seq[T] = Seq(seq, seq).flatten.slice(offset, offset + seq.size)
一种简单的方法是将序列与其自身连接起来,然后取所需的slice
:
(seq ++ seq).slice(start, start + seq.length)
这只是 drop
/take
版本的变体,但可能更清晰一些。
我可以 使用 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
浏览整个集合时,我想知道是否有更惯用的方法。递归方法可以让我避免任何 var
s。但基本上,我想知道是否可能出现以下情况:
seq.rotatedView(i)
这将创建旋转视图,如旋转位(或循环移位)。
是不是像下面这样:
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)
这应该以一种相当通用的方式进行,并允许任意旋转:
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, ?)
请记住,这些不一定都是性能最优化的,它们也不能用于无限集合(none 可以)。
根据 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)
这是一种衬里解决方案
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)
鉴于:
val seq = Seq(1,2,3,4,5)
解决方案:
seq.zipWithIndex.groupBy(_._2<3).values.flatMap(_.map(_._1))
或
seq.zipWithIndex.groupBy(_._2<3).values.flatten.map(_._1)
结果:
List(4, 5, 1, 2, 3)
- 如果旋转大于集合的长度 - 我们需要使用
rotation%length
,如果负数小于公式(rotation+1)%length
并取绝对值。 - 效率不高
这是一种相当简单且惯用的 Scala 集合编写方式:
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)
我们可以简单地使用foldLeft
来反转列表,如下所示。
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)
另一种尾递归方法。当我用 JMH 对它进行基准测试时,它比基于 drop/take:
的解决方案快大约 2 倍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)
这是一段简单的代码
object tesing_it extends App
{
val one = ArrayBuffer(1,2,3,4,5,6)
val i = 2 //the number of index you want to move
for(z<-0 to i){
val y = 0
var x = one += one(y)
x = x -= x(y)
println("for seq after process " +z +" " + x)
}
println(one)
}
结果:
for seq after process 0 ArrayBuffer(2, 3, 4, 5, 6, 1)
for seq after process 1 ArrayBuffer(3, 4, 5, 6, 1, 2)
for seq after process 2 ArrayBuffer(4, 5, 6, 1, 2, 3)
ArrayBuffer(4, 5, 6, 1, 2, 3)
如果您不需要验证 "offset" 的另一种解决方案:
def rotate[T](seq: Seq[T], offset: Int): Seq[T] = Seq(seq, seq).flatten.slice(offset, offset + seq.size)
一种简单的方法是将序列与其自身连接起来,然后取所需的slice
:
(seq ++ seq).slice(start, start + seq.length)
这只是 drop
/take
版本的变体,但可能更清晰一些。