2

我一直在尝试在wikipedia上重新创建 Burrows-Wheeler 变换的示例。为了增加乐趣，我试图通过递归策略来做到这一点。但是，我陷入了第一步，创建了字符串的所有旋转。这是我的代码：

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|^

我已经盯着这个有一段时间了，虽然问题应该是相当直接的，但我似乎无法弄清楚。你能看出我做错了什么吗？

4

2 回答 2

3

这是一个较短的函数，它不使用递归，但在计算中也是如此。

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)
于 2012-11-27T22:59:33.027 回答
2

当您将 splitIndex 一个字符移到前面时，您必须将其应用于原始字符串：

newString :: transformString(string, splitIndex - 1)

另一种解决方案是删除拆分索引参数并始终拆分最后一个字符，但是您必须再次将其应用于转换后的字符串。

于 2012-11-27T18:20:22.943 回答