kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

「こんなプログラムを書いてみよう」 in Scala

http://d.hatena.ne.jp/nowokay/20080717#1216294670

とりあえず、こんな感じかな(k文字版)。効率は度外視して、サクっと書ける書き方で書いてみた。

object S {
  def strings(list: List[String]): List[String] = {
    def g(prefix: String, list: List[String]): List[String] = {
      list match {
        case Nil => List(prefix)
        case _ =>
          for(s <- list if (s indexOf prefix) == 0; 
              r <- g(s substring 1, list - s)) yield s(0) + r
      }
    }
    g("", list)
  }
}

実行結果。

scala> :load strings.scala
Loading strings.scala...
defined module S

scala> import S._
import S._

scala> strings(List("ABA", "BAB", "ABC", "BCA", "CAB", "CAA", "AAB"))
res0: List[String] = List(CABABCAAB, CABCAABAB, CAABABCAB, CAABCABAB)