Recursive create all rotations of string in scala

Question

I've been playing around with trying to recreate the example of the Burrows-Wheeler transform on wikipedia. To add to the fun I'm trying to do so by a recursive strategy. However, I get stuck in the first step, creating all rotations of the string. Here's my code:

object SimpleBW extends App {

  val string = "^BANANA|"

  val list = tranformStringStart(string)
  list.foreach(println)

  def tranformStringStart(string: String): List[String] = { transformString(string, string.length) }

  def transformString(string: String, splitIndex: Int): List[String] = {
    if (splitIndex == 0) {
      // Recursion base case
      Nil
    } else {
      val (firstString, secondString) = string.splitAt(splitIndex)
      val newString = secondString + firstString
      newString :: transformString(secondString + firstString, splitIndex - 1)
    }
  }

}

This generates the following output:

^BANANA|
|^BANANA
NA|^BANA
ANANA|^B
A|^BANAN
BANANA|^
NANA|^BA
ANA|^BAN

Which is similar to the wikipedia example, but not identical, and I can't seem to figure out why. According to the example the output should look like this:

^BANANA|
|^BANANA
A|^BANAN
NA|^BANA
ANA|^BAN
NANA|^BA
ANANA|^B
BANANA|^

I've been staring at this for some while now, and while the problem should be fairly straight forward, I can't seem to figure it out. Can you spot what I'm doing wrong?

Answer 1

As you are moving your splitIndex one character to the front you have to apply it to the original string:

newString :: transformString(string, splitIndex - 1)

Another solution would be to remove the split index param and always split off the last character, but then you have to apply it to the transformed string again.

Answer 2

Here is a shorter function which doesn't use recursion but does the same in computation.

def transformString(s:String):List[String] = 
  for(i <- s.length until 0 by - 1 toList) yield s.drop(i)+ s.take(i)

Another one:

def transformString(s:String):List[String] = s.inits.toList zip(s.tails.toSeq.reverse) map(z=> z._2+z._1)