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