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とか使っちゃったけどあんまり良くない気がする。
//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: " + )