Рекурсивно создавать все повороты строки в Scala

Question

Я пытался воссоздать пример преобразования Барроуза-Уилера в Википедии. Чтобы добавить к веселью, я пытаюсь сделать это с помощью рекурсивной стратегии. Тем не менее, я застреваю на первом этапе, создавая все повороты строки. Вот мой код:

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)
    }
  }

}

Это создает следующий вывод:

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

Что похоже на пример из Википедии, но не идентично, и я не могу понять, почему. Согласно примеру вывод должен выглядеть так:

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

Я уже давно смотрю на это, и, хотя проблема должна быть довольно простой, я не могу понять это. Можете ли вы определить, что я делаю не так?

Answer 1

Когда вы перемещаете ваш splitIndex на один символ вперед, вы должны применить его к исходной строке:

newString :: transformString(string, splitIndex - 1)

Другое решение состоит в том, чтобы удалить параметр индекса разбиения и всегда отделять последний символ, но затем вам придется применить его к преобразованной строке снова.

Answer 2

Вот более короткая функция, которая не использует рекурсию, но делает то же самое в вычислениях.

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

Другой:

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