S-99を解く。P25から先がちょいむず。
P26
組み合わせを求めるというオーソドックスな問題。n個からr個を選ぶ組み合わせは再帰的に考えると
- (取り出したものを加える場合)は n-1個からr-1個を選ぶ
- (取り出したものを加えない場合)はn-1個からr個を選ぶ
上記2つのパターンの和になるので、これで再帰させる。
def flatten(ls: List[Any]): List[Any] = ls flatMap { case ms: List[_] => flatten(ms) case e => List(e) } def combinations(n:Int, ls:List[Any]): List[List[Any]] = if (n==0) List(Nil) else if (ls == Nil) List(Nil) else ((combinations(n-1,ls.tail) map ((e:List[Any]) => ls.head :: flatten(e))) ::: combinations(n,ls.tail)) println(combinations(3, List('a, 'b, 'c, 'd)) filter (l => l.length == 3)) println(combinations(3, List('a, 'b, 'c, 'd)))
結局r個以下の組み合わせを出力する関数になってしまった。しょうがないのでfilterかましてるけど。 あと、型がうまく決められなかったので、Anyとか使っちゃったけどあんまり良くない気がする。
Scalaスケーラブルプログラミング第2版//21 def insertAt[A](e:A, n:Int, ls:List[A]): List[A] = { val v = ls.splitAt(n) v._1 ::: e :: v._2 } println("s21: "+ insertAt('new, 1, List('a, 'b, 'c, 'd))) //22 def range(s:Int, e:Int): List[Int] = List.range(s,e+1) println("s22: " + range(4, 9)) //23 Randomの使い方を知らなかった def removeAt[A](n:Int, ls:List[A]): (List[A],A) = { val v = ls.splitAt(n) (v._1 ::: v._2.tail, v._2.head) } def randomSelect[A](n: Int, ls: List[A]): List[A] = if (n <= 0) Nil else { val (rest, e) = removeAt((new util.Random).nextInt(ls.length), ls) e :: randomSelect(n - 1, rest) } println("s23: " + randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h))) //24 def lotto(n: Int, r: Int): List[Int] = if (n <=0) Nil else randomSelect(n, List.range(1,r+1)) println("s24: " + lotto(6, 49)) //25 def randomPermute[A](ls:List[A]): List[A] = lotto(ls.length,ls.length) map(e => ls(e-1)) println("s25: " + randomPermute(List('a, 'b, 'c, 'd, 'e, 'f))) //26 //def combinations[A](n:Int, ls:List[A]): List[List[Any]] = // if (n == 0) Nil // else if (ls == Nil) Nil // else ( ls.head :: combinations(n-1,ls.tail) ) :: combinations(n,ls.tail) def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = ls match { case Nil => Nil case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f) } def combinations[A](n: Int, ls: List[A]): List[List[A]] = if (n == 0) List(Nil) else flatMapSublists(ls) { sl => combinations(n - 1, sl.tail) map {sl.head :: _} } println("s26: " + combinations(3, List('a, 'b, 'c, 'd, 'e, 'f))) //27 //println("s27: " + ) //28 //println("s28: " + )