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