遞歸在scala中創建字符串的所有旋轉

我一直在嘗試重新創建wikipedia上的Burrows-Wheeler轉換的示例。爲了增加樂趣，我試圖通過遞歸策略來實現。但是，我陷入了第一步，創建了字符串的所有旋轉。這裏是我的代碼：遞歸在scala中創建字符串的所有旋轉

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

我一直在盯着這一段，而現在，雖然這個問題應該是相當簡單的，我似乎無法推測出來。你能發現我做錯了什麼嗎？

來源

2012-11-27 Johan

當你在一個字符移動你splitIndex你必須把它應用到原始字符串前：

newString :: transformString(string, splitIndex - 1)

另一種解決方案是取消拆分指數PARAM始終分裂出去的最後一個字符，但是你必須再次將它應用於轉換後的字符串。

來源

2012-11-27 18:20:22 CQQL

這是一個較短的函數，它不使用遞歸但在計算中也是這樣。

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-27 22:59:33

遞歸在scala中創建字符串的所有旋轉

回答

相關問題