年俸1000万の会社の試験問題

Scalaで。
selection関数の参考にさせていただいたサイトを失念・・・。

/**

 4種類のアルファベット "A,C,G,T" から成るn文字の文字列のうち、"AAG"とい
う並びが含まれる文字列を全て列挙するプログラムを書きなさい。ただし、nは
3以上の整数とし、文字列内に同じアルファベットが出現しても構わないものと
し、出力順序は問わないものとします。

http://alpha.cgios.net/alpha/cgios

 * n == 3 => 1
 * n == 4 => 8
 * n == 5 => 48

 */

val l = List("A","C","G","T")

// 重複組合せを得る
def selection[T](a :List[T], n :Int) :Iterator[List[T]] =
    (a, n) match {
        case (_, 0) => Iterator(Nil)
        case (Nil, _) => Iterator()
        case _ => selection(a, n - 1).map(a.head :: _) ++ selection(a.tail, n)
}

// 重複組わせの各要素ごとに、順列組合せを求め、そこから該当文字列を持つもののみ抽出する
def solve(n: Int,s:String): Iterator[String] =
  selection(l,n).map(_.permutations).flatten.map(_.mkString("")).filter(_.contains(s))

こんな実装もあるんだなぁ。
http://d.hatena.ne.jp/clams/20100919/p1