scalarecursionburrows-wheeler-transform

Recursive create all rotations of string in scala


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?


Solution

  • 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.