2

ウィキペディアで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 を 1 文字前に移動しているので、元の文字列に適用する必要があります。

newString :: transformString(string, splitIndex - 1)

別の解決策は、分割インデックス パラメータを削除し、常に最後の文字を分割することですが、変換された文字列に再度適用する必要があります。

于 2012-11-27T18:20:22.943 に答える