Best practice for shifting a sequence in a circular manner

Question

I have to implement a kind of an array or sequence or list, which supports the cheapest way of circulated forwarding and back winding of elements. See this example:

Original sequence: 1 2 3 4 5

Forwarded once: 5 1 2 3 4
Forwarded twice: 4 5 1 2 3

Same but opposite is for the back winding. What would be the cheapest and most Scala-style way of implementing this? In Java I could use LinkedList and it would do great... However, I could not find any definite answer for Scala.

Also, it also has to be easy to replace any given element by index, as in LinkedList.

UPDATE:

For the fastest, but not-so-idiomatic variant of algorithm (you know when you need it), refer to the answer of Petr Pudlák!!!

Ninetieth

this migth be usefull for you – Enuresis

I think "barrel shifting" might be a more technical way to express your intent than "circulating"... – Cockaigne

@Cockaigne I only know this term from the logic circuit. Thus it's a particular implementation. You're sure this applies to the operation of shifting? – Geminate

@Geminate I think you are right, I might have confused the HW term for the circular shifting... Anyway, the verb should be shift, not circulate (that is what I found weird in the title). Cheers. – Cockaigne

Answer 1

Immutable implementation

A ring buffer is a pair of an IndexedSeq and an Int pointer into this sequence. I provide code for a immutable version. Note that not all methods that might be useful are implemented; like the mutators that change the content of the IndexedSeq.

With this implementation, shifting is just creating one new object. So it's pretty efficient.

Example code

class RingBuffer[A](val index: Int, val data: IndexedSeq[A]) extends IndexedSeq[A] {
  def shiftLeft = new RingBuffer((index + 1) % data.size, data)
  def shiftRight = new RingBuffer((index + data.size - 1) % data.size, data)
  def length = data.length
  def apply(i: Int) = data((index + i) % data.size)
}

val rb = new RingBuffer(0, IndexedSeq(2,3,5,7,11))

println("plain: " + rb)
println("sl: " + rb.shiftLeft)
println("sr: " + rb.shiftRight)

Output

plain: Main(2, 3, 5, 7, 11)
sl: Main(3, 5, 7, 11, 2)
sr: Main(11, 2, 3, 5, 7)

Performance comparison to mutable implementations

The OP mentions that you should look at the mutable implementations (e.g. this answer), if you need performance. This is not true in general. As always: It depends.

Immutable

• update: O(log n), which is basically the update complexity of the underlying IndexedSeq;
• shifting: O(1), also involves creating a new object which may cost some cycles

Mutable

• update: O(1), array update, as fast as it gets
• shifting: O(n), you have to touch every element once; fast implementations on primitive arrays might still win against the immutable version for small arrays, because of constant factor

Geminate

Anyone knowing why the println shows the data structure as Main? I've run it as a script using the scala command. – Geminate

Method stringPrefix from TraversableLike defines prefix of collection as substring of class name between last . and first $. I can't check now, but I think because of scala command class loading magic your class receives a name like Main$object$$iw$$iw$RingBuffer which gives prefix Main. Try this in REPL: settings.unwrapStrings = false; class Foo; println(new Foo); – Ingle

What version of scala are you using? In 2.9.0.1 in the REPL it prints as plain: (2, 3, 5, 7, 11). You can get the correct prefix with override def stringPrefix = "RingBuffer". – Source

This is really cool because data is only needed exactly once in memory, all of the RingBuffers can share the one copy (assuming immutability). – Boarhound

Answer 2

scala> val l = List(1,2,3,4,5)
l: List[Int] = List(1, 2, 3, 4, 5)

scala> val reorderings = Stream.continually(l.reverse).flatten.sliding(l.size).map(_.reverse)
reorderings: Iterator[scala.collection.immutable.Stream[Int]] = non-empty iterator

scala> reorderings.take(5).foreach(x => println(x.toList))
List(1, 2, 3, 4, 5)
List(5, 1, 2, 3, 4)
List(4, 5, 1, 2, 3)
List(3, 4, 5, 1, 2)
List(2, 3, 4, 5, 1)

Scleritis

Nice idea! Functional. Efficient? – Paneling

I find the type of reorderings weird. An Iterator of Streams? – Detest

Answer 3

I needed such an operation myself, here it is. Method rotate rotates the given indexed sequence (array) to the right (negative values shift to the left). The process is in-place, so no additional memory is required and the original array is modified.

It's not Scala-specific or functional at all, it's meant to be very fast.

import annotation.tailrec;
import scala.collection.mutable.IndexedSeq

// ...

  @tailrec
  def gcd(a: Int, b: Int): Int =
    if (b == 0) a
    else gcd(b, a % b);

  @inline
  def swap[A](a: IndexedSeq[A], idx: Int, value: A): A = {
    val x = a(idx);
    a(idx) = value;
    return x;
  }

  /**
   * Time complexity: O(a.size).
   * Memory complexity: O(1).
   */
  def rotate[A](a: IndexedSeq[A], shift: Int): Unit =
    rotate(a, 0, a.size, shift);
  def rotate[A](a: IndexedSeq[A], start: Int, end: Int, shift: Int): Unit = {
    val len = end - start;
    if (len == 0)
      return;

    var s = shift % len;
    if (shift == 0)
      return;
    if (s < 0)
      s = len + s;

    val c = gcd(len, s);
    var i = 0;
    while (i < c) {
      var k = i;
      var x = a(start + len - s + k);
      do {
        x = swap(a, start + k, x);
        k = (k + s) % len;
      } while (k != i);
      i = i + 1;
    }
    return;
  }

Voluntary

Answer 4

The way I solve Scala problems is solving them in Haskell first, and then translating. :)

reorderings xs = take len . map (take len) . tails . cycle $ xs
  where len = length xs

This is the easiest way I could think of, which produces the list of all possible shifts, by "shifting left" repeatedly.

ghci> reorderings [1..5]
[[1,2,3,4,5],[2,3,4,5,1],[3,4,5,1,2],[4,5,1,2,3],[5,1,2,3,4]]

The concept is relatively simple (for those comfortable with functional programming, that is). First, cycle the original list, producing an infinite stream from which to draw from. Next, break that stream into a stream of streams, where each subsequent stream has dropped the first element of the previous stream (tails). Next, limit each substream to the length of the original list (map (take len)). Finally, limit the stream of streams to the length of the original list, since there are only len possible reorderings (take len).

So let's do that in Scala now.

def reorderings[A](xs: List[A]):List[List[A]] = {
  val len = xs.length
  Stream.continually(xs).flatten // cycle
    .tails
    .map(_.take(len).toList)
    .take(len)
    .toList
}

We just had to use a small workaround for cycle (not sure if Scala standard libs provide cycle, though I was pleasantly surprised to find they provide tails), and a few toLists (Haskell lists are lazy streams, while Scala's are strict), but other than that, it's exactly the same as the Haskell, and as far as I can tell, behaves exactly the same. You can almost think of Scala's . as behaving like Haskell's, except flowing the opposite way.

Also note this is very nearly the same as dhg's solution, except without the reverses, which (on the upside) makes it more efficient, but (on the downside) provides the cycles in "backwinding" order, rather than "forward" order.

Boarhound

An interesting thought! Frankly speaking, I am trying to master FP now and my initial choices of languages to learn were Scala and Haskell and eventually, Clojure. What I know of Haskell so far also made me think that it is a good practice - to formulate a solution in it and then translate to Scala))) But I am yet far from being perfect in FP, so thanks for mentioning that parallel with an example. That will make me more conscious of it! – Ninetieth

Answer 5

Nice combination of @dhg and @Roman Zykov versions:

scala> val l = List(1,2,3,4,5)
l: List[Int] = List(1, 2, 3, 4, 5)

scala> val re = Stream continually (l ++ l.init sliding l.length) flatten
re: scala.collection.immutable.Stream[List[Int]] = Stream(List(1, 2, 3, 4, 5), ?)

scala> re take 10 foreach println
List(1, 2, 3, 4, 5)
List(2, 3, 4, 5, 1)
List(3, 4, 5, 1, 2)
List(4, 5, 1, 2, 3)
List(5, 1, 2, 3, 4)
List(1, 2, 3, 4, 5)
List(2, 3, 4, 5, 1)
List(3, 4, 5, 1, 2)
List(4, 5, 1, 2, 3)
List(5, 1, 2, 3, 4)

Catabolite

Answer 6

There is a very simple solution:

val orderings = List(1,2,3,4,5)
(orderings ++ orderings.dropRight(1)).sliding(orderings.length).toList

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

Selfexpression

Answer 7

My take on it:

@tailrec
 def shift(times:Int, data:Array[Int]):Array[Int] = times match {
        case t:Int if(t <= 0) => data;
        case t:Int if(t <= data.length) => shift(0, (data++data.take(times)).drop(times)) 
        case _ => shift(times % data.length, data);
}

Presentation

Answer 8

Here is one possible solution for sequences

// imports required for: `Scala 2.13.10 (OpenJDK 64-Bit Server VM, Java 1.8.0_292)`
import scala.language.implicitConversions
import scala.language.postfixOps

class ShiftWarper( seq: Seq[ Int ] ) {
  def shiftLeft: Seq[ Int ] = if ( seq.isEmpty ) {
      seq
    } else {
      seq.tail :+ seq.head
    }
  def shiftRight: Seq[ Int ] = if ( seq.isEmpty ) {
      seq
    } else {
      seq.last +: seq.init
    }
}
implicit def createShiftWarper( seq: Seq[ Int ] ) =
    new ShiftWarper( seq ) 

def shift_n_Times(
  times: Int,
  seq: Seq[ Int ],
  operation: Seq[ Int ] => Seq[ Int ] ): Seq[ Int ] = if ( times > 0 ) {
    shift_n_Times(
      times - 1,
      operation( seq ),
      operation )
  } else {
    seq
  }

// main: unit test
val initialSeq = ( 0 to 9 )
// > val initialSeq: scala.collection.immutable.Range.Inclusive = Range 0 to 9
( initialSeq shiftLeft ) shiftRight
// > val res1: Seq[Int] = Vector(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
shift_n_Times(
  5,
  initialSeq,
  initialSeq => new ShiftWarper( initialSeq ).shiftRight )
// > val res2: Seq[Int] = Vector(5, 6, 7, 8, 9, 0, 1, 2, 3, 4)

Canso

Answer 9

Here's another simple scala solution for shifting a Stream right or left by arbitrary amounts. "Cycle" repeats the stream infintely, then "shift" finds the correct slice. "posMod" allows you to shift by an index larger than xs.length but without actually straying more than xs.length elements in the infinite Stream:

scala> def posMod(a:Int, b:Int) = (a % b + b) % b

scala> def cycle[T](xs : Stream[T]) : Stream[T] = xs #::: cycle(xs)

scala> def shift[T](xs:Stream[T], x: Int) = cycle(xs)
          .drop(posMod(x, xs.length))
          .take(xs.length)

Then:

scala> shift(Stream(1,2,3,4), 3).toList
--> List[Int] = List(4, 1, 2, 3)

scala> shift(Stream(1,2,3,4), -3).toList
--> List[Int] = List(2, 3, 4, 1)

scala>  shift(Stream(1,2,3,4), 30000001).toList
--> List[Int] = List(2, 3, 4, 1)

Philbin

I think my shifting left with a positive number and right with a negative number is the opposite of the way the question is worded, where "forward" moves right, but you get the idea. – Philbin

Answer 10

My proposition:

def circ[A]( L: List[A], times: Int ): List[A] = {
    if ( times == 0 || L.size < 2 ) L
    else circ(L.drop(1) :+ L.head , times-1)
}

val G = (1 to 10).toList
println( circ(G,1) ) //List(2, 3, 4, 5, 6, 7, 8, 9, 10, 1)
println( circ(G,2) ) //List(3, 4, 5, 6, 7, 8, 9, 10, 1, 2)
println( circ(G,3) ) //List(4, 5, 6, 7, 8, 9, 10, 1, 2, 3)
println( circ(G,4) ) //List(5, 6, 7, 8, 9, 10, 1, 2, 3, 4)

Bamford

Answer 11

You can instantiate a function that will include the Array(A) and the number of rotation steps that you need(S):

def rotate(A: Array[Int], S: Int): Int = { (A drop A.size - (S % A.size)) ++ (A take A.size - (S % A.size)) }

rotate(Array(1, 2, 3, 4, 5), 1)

Halfandhalf