2 つのリスト xs, ys を受け取り、各々の要素に対して関数 f を適用し、その結果をリストに格納して返すマップ関数 zipWith を定義してください。リストの長さが異なる場合、短いほうのリストに合わせるものとします。
def zipWith[A, B, C](f: (A, B) => C)(xs: List[A], List[B]): List[C]
scala> zipWith((_:Int) + (_:Int))(List(1, 2, 3, 4), List(5, 6, 7, 8)) val res0: List[Int] = List(6, 8, 10, 12) scala> zipWith(List(_: Int, _: Int))(List(1, 2, 3, 4), List(5, 6, 7, 8)) val res1: List[List[Int]] = List(List(1, 5), List(2, 6), List(3, 7), List(4, 8))
2 つのリスト xs, ys を畳み込む関数 foldl2 と foldr2 を定義してください。foldl2 はリストの左側 (先頭) から、foldr2 はリストの右側 (末尾) から畳み込みを行います。リストの長さが異なる場合、短いほうのリストに合わせるものとします。
def foldl2[A, B, C](f: (A, B, C) => A)(a: A)(xs: List[B], ys: List[C]): A def foldr2[A, B, C](f: (A, B, C) => C)(a: C)(xs: List[A], ys: List[B]): C
scala> foldl2((a: Int, x: Int, y: Int) => x * y + a)(0)(List(1, 2, 3, 4), List(5, 6, 7, 8)) val res0: Int = 70 scala> foldr2((x: Int, y: Int, a: Int) => x * y + a)(0)(List(1, 2, 3, 4), List(5, 6, 7, 8)) val res1: Int = 70 scala> foldl2((a: List[Int], x: Int, y: Int) => x * y :: a)(Nil: List[Int])(List(1, 2, 3, 4), List(5, 6, 7, 8)) val res2: List[Int] = List(32, 21, 12, 5) scala> foldr2((x: Int, y: Int, a: List[Int]) => x * y :: a)(Nil: List[Int])(List(1, 2, 3, 4), List(5, 6, 7, 8)) val res3: List[Int] = List(5, 12, 21, 32)
整数 n を 1 以上の自然数の和で表すことを考えます。これを「整数の分割」といいます。整数を分割するとき、同じ自然数を何回使ってもかまいませんが、並べる順序が違うだけのものは同じ分割とします。簡単な例を示します。
n = 6
6 分割 : 1 + 1 + 1 + 1 + 1 + 1
5 分割 : 1 + 1 + 1 + 1 + 2
4 分割 : 1 + 1 + 1 + 3
1 + 1 + 2 + 2
3 分割 : 1 + 1 + 4
1 + 2 + 3
2 + 2 + 2
2 分割 : 1 + 5
2 + 4
3 + 3
1 分割 : 6
6 の場合、分割の仕方は 11 通りあります。この数を「分割数」といいます。自然数 n の分割数を求める関数 partitionNumber を定義してください。
def partitionNumber(n: Int): BigInt
scala> partitionNumber(1) val res0: BigInt = 1 scala> partitionNumber(2) val res1: BigInt = 2 scala> partitionNumber(3) val res2: BigInt = 3 scala> partitionNumber(4) val res3: BigInt = 5 scala> partitionNumber(5) val res4: BigInt = 7 scala> partitionNumber(10) val res5: BigInt = 42 scala> partitionNumber(20) val res6: BigInt = 627 scala> partitionNumber(50) val res7: BigInt = 204226
整数 n の分割の仕方をすべて求める関数 partitionOfInt を定義してください。
def partitionOfInt(f: List[Int] => Unit, n: Int): Unit
scala> partitionOfInt(println, 5) List(1, 1, 1, 1, 1) List(2, 1, 1, 1) List(2, 2, 1) List(3, 1, 1) List(3, 2) List(4, 1) List(5) scala> partitionOfInt(println, 6) List(1, 1, 1, 1, 1, 1) List(2, 1, 1, 1, 1) List(2, 2, 1, 1) List(2, 2, 2) List(3, 1, 1, 1) List(3, 2, 1) List(3, 3) List(4, 1, 1) List(4, 2) List(5, 1) List(6)
リストで表した集合 ls を分割することを考えます。たとえば、集合 (1 2 3) は次のように分割することができます。
1 分割 : ((1 2 3)) 2 分割 : ((1 2) (3)), ((1 3) (2)), ((1) (2 3)) 3 分割 ; ((1) (2) (3))
このように、分割した集合 xs は元の集合 ls の部分集合になります。分割した部分集合の積は空集合になり、分割した部分集合のすべての和を求めると元の集合になります。
ls の分割の仕方をすべて求める関数 parititonOfSet を定義してください。
def partitionOfSet[A](f: List[List[A]] => Unit, ls: List[A]): Unit
scala> partitionOfSet(println, List(1, 2, 3)) List(List(1), List(2), List(3)) List(List(1, 2), List(3)) List(List(1, 3), List(2)) List(List(1), List(2, 3)) List(List(1, 2, 3)) scala> partitionOfSet(println, List(1, 2, 3, 4)) List(List(1), List(2), List(3), List(4)) List(List(1, 2), List(3), List(4)) List(List(1, 3), List(2), List(4)) List(List(1, 4), List(2), List(3)) List(List(1), List(2, 3), List(4)) List(List(1, 2, 3), List(4)) List(List(1, 4), List(2, 3)) List(List(1), List(2, 4), List(3)) List(List(1, 2, 4), List(3)) List(List(1, 3), List(2, 4)) List(List(1), List(2), List(3, 4)) List(List(1, 2), List(3, 4)) List(List(1, 3, 4), List(2)) List(List(1), List(2, 3, 4)) List(List(1, 2, 3, 4))
集合を分割する方法の総数を「ベル数 (Bell Number)」といい、次の漸化式で求めることができます。
ベル数を求める関数 bellNumber を定義してください。
def bellNumber(n: Int): BigInt
scala> for (i <- 0 to 10) println(bellNumber(i)) 1 1 2 5 15 52 203 877 4140 21147 115975 scala> bellNumber(50) val res0: BigInt = 185724268771078270438257767181908917499221852770
n 個の整数 1, 2, ..., n の順列を考えます。先頭の要素を 1 から数えることとすると、i 番目の要素が整数 i ではない順列を「完全順列」といいます。1 から n までの整数値で完全順列を生成する関数 derangement を定義してください。
def derangement(f: List[Int] => Unit, n: Int): Unit
scala> derangement(println, 3) List(2, 3, 1) List(3, 1, 2) scala> derangement(println, 4) List(2, 1, 4, 3) List(2, 3, 4, 1) List(2, 4, 1, 3) List(3, 1, 4, 2) List(3, 4, 1, 2) List(3, 4, 2, 1) List(4, 1, 2, 3) List(4, 3, 1, 2) List(4, 3, 2, 1)
完全順列の総数を「モンモール数 (Montmort number)」といいます。モンモール数は次の漸化式で求めることができます。
モンモール数を求める関数 montmortNumber を定義してください。
def montmortNumber(n: Int): BigInt
scala> montmortNumber(1) val res0: BigInt = 0 scala> montmortNumber(2) val res1: BigInt = 1 scala> montmortNumber(3) val res2: BigInt = 2 scala> montmortNumber(4) val res3: BigInt = 9 scala> montmortNumber(5) val res4: BigInt = 44 scala> montmortNumber(10) val res5: BigInt = 1334961 scala> montmortNumber(20) val res6: BigInt = 895014631192902121
バランスの取れた n 対のカッコ列を生成する関数 kakko を定義してください。カッコ列は ( と ) からなる列のことで、バランスが取れているカッコ列は、右カッコで閉じることができる、つまり右カッコに対応する左カッコがある状態のことをいいます。たとえば n = 1 の場合、( ) はバランスの取れたカッコ列ですが、) ( はバランスが取れていません。
def kakko(f: String => Unit, n: Int): Unit
scala> kakko(println, 3) ((())) (()()) (())() ()(()) ()()() scala> kakko(println, 4) (((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()()
バランスの取れた n 対のカッコ列の総数を求める関数 kakkoNum を定義してください。
def kakkoNum(n: Int): BigInt
scala> kakkoNum(1) val res4: BigInt = 1 scala> kakkoNum(2) val res5: BigInt = 2 scala> kakkoNum(3) val res6: BigInt = 5 scala> kakkoNum(4) val res7: BigInt = 14 |
scala> kakkoNum(5) val res8: BigInt = 42 scala> kakkoNum(10) val res9: BigInt = 16796 scala> kakkoNum(20) val res10: BigInt = 6564120420 scala> kakkoNum(50) val res11: BigInt = 1978261657756160653623774456 |
リスト : マッピング
def zipWith[A, B, C](f: (A, B) => C)(xs: List[A], ys: List[B]): List[C] =
(xs, ys) match {
case (Nil, _) | (_, Nil) => Nil
case (x::xs1, y::ys1) => f(x, y) :: zipWith(f)(xs1, ys1)
}
// 別解
def zipWith1[A, B, C](f: (A, B) => C)(xs: List[A], ys: List[B]): List[C] =
for ((x, y) <- (xs zip ys)) yield f(x, y)
zipWith は 2 つのリストの先頭要素 x, y を取り出し、f(x, y) を呼び出してその返り値をリストに追加していくだけです。どちらかのリストが空リストになったときが再帰呼び出しの停止条件になります。別解は for 内包表記で書き直したものです。メソッド zip で 2 つのリストをひとつにまとめて、それを for 式で取り出して f(x, y) を呼び出します。
リスト : 畳み込み
def foldl2[A, B, C](f: (A, B, C) => A)(a: A)(xs: List[B], ys: List[C]): A =
(xs, ys) match {
case (Nil, _) | (_, Nil) => a
case (x::xs1, y::ys1) => foldl2(f)(f(a,x,y))(xs1, ys1)
}
def foldr2[A, B, C](f: (A, B, C) => C)(a: C)(xs: List[A], ys: List[B]): C =
(xs, ys) match {
case (Nil, _) | (_, Nil) => a
case (x::xs1, y::ys1) => f(x, y, foldr2(f)(a)(xs1, ys1))
}
foldl2, foldr2 も簡単です。foldl2 は再帰呼び出しをするときに累積変数の値を関数 f で更新します。foldr2 は関数 f を呼び出すときに foldr2 を再帰呼び出しします。このとき、累積変数の値は更新しません。どちらかの引数が空リストになったときが再帰の停止条件です。
整数 n を k 以下の整数で分割する総数を求める関数を p(n, k) とすると、p(n, k) は次のように定義することができます。
たとえば、p(6, 6) は次のように計算することができます。
p(6, 6) => p(0, 6) + p(6, 5)
=> 1 + p(1, 5) + p(6, 4)
=> 1 + 1 + p(2, 4) + p(6, 3)
=> 1 + 1 + 2 + 7
=> 11
p(2, 4) => p(-2, 4) + p(2, 3)
=> 0 + p(-1, 3) + p(2, 2)
=> 0 + 0 + p(0, 2) + p(2, 1)
=> 0 + 0 + 1 + 1
=> 2
p(6, 3) => p(3, 3) + p(6, 2)
=> p(0, 3) + p(3, 2) + p(4, 2) + p(6, 1)
=> 1 + p(1, 2) + p(3, 1) + p(2, 2) + p(4, 1) + 1
=> 1 + 1 + 1 + p(0, 2) + p(2, 1) + 1 + 1
=> 1 + 1 + 1 + 1 + 1 + 1 + 1
=> 7
分割数を求める関数 partitionNumber は、関数 p(n, k) を使うと次のようにプログラムすることができます。
リスト : 分割数
def partitionNumber(n: Int): BigInt = {
def partNum(n: Int, k: Int): BigInt =
(n, k) match {
case (0, _) | (1, _) | (_, 1) => 1
case _ => if (n < 0 || k < 1) 0
else partNum(n - k, k) + partNum(n, k - 1)
}
//
partNum(n, n)
}
局所関数 partNum は p(n, k) の定義をそのままプログラムしただけです。ただし、このプログラムは二重再帰で何度も同じ値を求めているため実行速度はとても遅くなります。
動的計画法を使うと、大きな値でも高速に計算することができます。下の図を見てください。
大きさ n + 1 のベクタを用意します。ベクタの添字が n を表していて、p(n, 1) から順番に値を求めていきます。p(n, 1) の値は 1 ですから、ベクタの要素は 1 に初期化します。次に、p(n, 2) の値を求めます。定義により p(n, 2) = p(n - 2, 2) + p(n, 1) なので、2 番目以降の要素に n - 2 番目の要素を加算すれば求めることができます。あとは、k の値をひとつずつ増やして同様の計算を行えば p(n, n) の値を求めることができます。
k 1 : [1, 1, 1, 1, 1, 1, 1] 2 : [1, 1, 1+1=2, 1+1=2, 2+1=3, 2+1=3, 3+1=4] => [1, 1, 2, 2, 3, 3, 4] 3: [1, 1, 2, 1+2=3, 1+3=4, 2+3=5, 3+4=7] => [1, 1, 2, 3, 4, 5, 7] 4: [1, 1, 2, 3, 1+4=4, 1+5=6, 2+7=9] => [1, 1, 2, 3, 5, 6, 9 5: [1, 1, 2, 3, 5, 1+6=7, 1+9=10] => [1, 1, 2, 3, 5, 7, 10] 6: [1, 1, 2, 3, 5, 7, 10+1=11] => [1, 1, 2, 3, 5, 7, 11]
プログラムは次のようになります。
リスト : 別解 (動的計画法)
def partitionNumber1(n: Int): BigInt = {
val table = Array.fill(n + 1)(1: BigInt)
for (k <- 2 to n) {
for (m <- k to n) table(m) += table(m - k)
}
table(n)
}
説明をそのままプログラムしただけなので、とくに難しいところはないと思います。それでは実際に試してみましょう。
scala> partitionNumber1(100) val res8: BigInt = 190569292 scala> partitionNumber1(200) val res9: BigInt = 3972999029388 scala> partitionNumber1(500) val res10: BigInt = 2300165032574323995027 scala> partitionNumber1(1000) val res11: BigInt = 24061467864032622473692149727991 scala> partitionNumber1(2000) val res12: BigInt = 4720819175619413888601432406799959512200344166
リスト : 整数の分割
def partitionOfInt(f: List[Int] => Unit, n: Int): Unit = {
def partInt(n: Int, k: Int, xs: List[Int]): Unit = {
(n, k) match {
case (0, _) => f(xs.reverse)
case (1, _) => f((1::xs).reverse)
case (_, 1) => f((List.fill(n)(1) ++ xs).reverse)
case _ => {
partInt(n, k - 1, xs)
if (n - k >= 0) partInt(n - k, k, k::xs)
}
}
}
partInt(n, n, Nil)
}
基本的な考え方は partitionNumber と同じです。局所関数 partInt に累積変数 xs を追加して、選んだ数値を xs に格納していきます。n が 0 の場合は f(xs.reverse) を呼び出します。n が 1 の場合は xs に 1 を追加してから関数 f を呼び出します。k が 1 の場合は List.fill で要素が 1 で長さが n のリストを作成します。そして、それを演算子 ++ で xs と連結してから関数 f を呼び出します。
結果をリストに格納して返す場合は次のようになります。
リスト : 整数の分割 (2)
type List2[A] = List[List[A]]
type List3[A] = List[List[List[A]]]
def partitionOfInt1(n: Int): List2[Int] = {
def partInt(n: Int, k: Int, xs: List[Int], ys: List2[Int]): List2[Int] =
(n, k) match {
case (0, _) => (xs.reverse)::ys
case (1, _) => ((1::xs).reverse)::ys
case (_, 1) => ((List.fill(n)(1) ++ xs).reverse)::ys
case _ => {
val zs = partInt(n, k - 1, xs, ys)
if (n - k >= 0) partInt(n - k, k, k::xs, zs) else zs
}
}
//
partInt(n, n, Nil, Nil)
}
局所関数 partInt に累積変数 ys を追加します。関数 f を呼び出すかわりに、生成したリストを ys に格納して返すだけです。
簡単な実行例を示します。
scala> partitionOfInt1(5) val res0: yasp03.List2[Int] = List(List(5), List(4, 1), List(3, 2), List(3, 1, 1), List(2, 2, 1), List(2, 1, 1, 1), List(1, 1, 1, 1, 1)) scala> partitionOfInt1(6) val res1: yasp03.List2[Int] = List(List(6), List(5, 1), List(4, 2), List(4, 1, 1), List(3, 3), List(3, 2, 1), List(3, 1, 1, 1), List(2, 2, 2), List(2, 2, 1, 1), List(2, 1, 1, 1, 1), List(1, 1, 1, 1, 1, 1))
集合を分割するアルゴリズムは簡単です。たとえば、n - 1 個の要素 x1, ..., xn-1 を持つ集合を分割したところ、i 個の部分集合 S1, ..., Si が生成されたとしましょう。ここに、n 番目の要素 xn を追加すると、要素が n 個の集合を分割することができます。
新しい要素を追加する場合は次に示す手順で行います。
簡単な例を示しましょう。次の図を見てください。
() ─ ((1)) ─┬─ ((1 2)) ─┬─ ((1 2 3))
│ │
│ └─ ((1 2) (3))
│
└─ ((1) (2)) ─┬─ ((1 3) (2))
│
├─ ((1) (2 3))
│
└─ ((1) (2) (3))
図 : 集合 (1 2 3) を分割する
部分集合を格納するリストを用意します。最初、部分集合は空集合なので空リストに初期化します。次に、要素 1 を追加します。部分集合は空リストなので、手順 1 は適用できません。手順 2 を適用して新しい部分集合 (1) を追加します。
次に要素 2 を追加します。((1)) に 手順 1 を適用すると、部分集合 (1) に要素を追加して ((1 2)) になります。手順 2 を適用すると、新しい部分集合 (2) を追加して ((1) (2)) になります。最後に 3 を追加します。((1 2)) に手順 1 を適用すると ((1 2 3)) に、手順 2 を適用すると ((1 2) (3)) になります。((1) (2)) に手順 1 を適用すると ((1 3) (2)) と ((1) (2 3)) になり、手順 2 を適用すると ((1) (2) (3)) になります。
このように、簡単な方法で集合を分割することができます。実際にプログラムを作る場合、上図を木と考えて、深さ優先で木をたどると簡単です。次のリストを見てください。
リスト : 集合の分割
def remove[A](x: A, xs: List[A]): List[A] =
xs match {
case Nil => Nil
case y::ys => if (x == y) ys else y :: remove(x, ys)
}
def partitionOfSet[A](f: List2[A] => Unit, xs: List[A]): Unit = {
def partSet(xs: List[A], ys: List2[A]): Unit =
xs match {
case Nil => f(ys)
case x::xs1 => {
partSet(xs1, List(x)::ys)
for (y <- ys) partSet(xs1, (x::y)::remove(y, ys))
}
}
//
partSet(xs.reverse, Nil)
}
実際の処理は局所関数 partSet で行います。累積変数 ys に分割中のリストをセットします。最初の節が再帰呼び出しの停止条件で、関数 f(ys) を呼び出します。次の節で、部分集合に要素 x を追加します。最初に、新しい部分集合 List(x) を ys に追加します。
次に、for 式でリスト ys から要素 y を順番に取り出し、ys から y を取り除いたリストに x :: y を追加します。ただし、このままでは要素の並び方が逆順になるので、partSset を呼び出す前に reverse でリスト xs を反転しています。これで集合の分割をすべて求めることができます。結果をリストに格納する場合は次のようになります。
リスト : 集合の分割 (2)
type List3[A] = List[List[List[A]]]
def partitionOfSet1[A](xs: List[A]): List3[A] = {
def partSet(xs: List[A], ys: List2[A], zs: List3[A]): List3[A] =
xs match {
case Nil => ys::zs
case x::xs1 => {
val b = partSet(xs1, List(x)::ys, zs)
ys.foldRight(b)((y: List[A], a: List3[A]) => partSet(xs1, (x::y)::remove(y, ys), a))
}
}
//
partSet(xs.reverse, Nil, Nil)
}
局所変数 partSet に累積変数 zs を追加します。そして、累積変数 ys に分割中のリストをセットし、完成したリストを累積変数 zs に格納して返すだけです。
簡単な実行例を示します。
scala> partitionOfSet1(List(1, 2, 3)) val res0: yasp03.List3[Int] = List(List(List(1, 2, 3)), List(List(1), List(2, 3)), List(List(1, 2), List(3)), List(List(1, 3), List(2)), List(List(1), List(2), List(3))) scala> partitionOfSet1(List(1, 2, 3, 4)) val res1: yasp03.List3[Int] = List(List(List(1, 2, 3, 4)), List(List(1), List(2, 3, 4)), List(List(1, 2), List(3, 4)), List(List(1, 3, 4), List(2)), List(List(1), List(2), List(3, 4)), List(List(1, 2, 3), List(4)), List(List(1, 4), List(2, 3)), List(List(1), List(2, 3), List(4)), List(List(1, 2, 4), List(3)), List(List(1, 3), List(2, 4)), List(List(1), List(2, 4), List(3)), List(List(1, 2), List(3), List(4)), List(List(1, 3), List(2), List(4)), List(List(1, 4), List(2), List(3)), List(List(1), List(2), List(3), List(4)))
リスト : ベル数
def combNum(n: Int, r: Int): BigInt =
if (n == r || r == 0) 1
else combNum(n, r - 1) * (n - r + 1) / r
def bellNumber(n: Int): BigInt = {
def iter(i: Int, xs: List[BigInt]): BigInt =
if (n == i) xs.head
else {
val ys = (for (k <- 0 to i) yield combNum(i, k)).toList
iter(i + 1, zipWith((_: BigInt) * (_: BigInt))(xs, ys).sum :: xs)
}
//
iter(0, List(1))
}
bellNumber は公式をそのままプログラムするだけです。実際の処理は局所関数 iter で行います。第 2 引数は累積変数で、ベル数を逆順で格納します。nＣk は関数 combNum と for 式で求めます。nＣk * B(k) の総和は zipWith と sum で計算します。累積変数は逆順になっていますが、二項係数は nＣi と nＣn - i の値が同じになるので、そのまま計算しても大丈夫です。
リスト : 完全順列
def derangement(f: List[Int] => Unit, n: Int): Unit = {
def permSub(n: Int, xs: List[Int], ys: List[Int]): Unit = {
xs match {
case Nil => f(ys.reverse)
case _ => for (x <- xs if (x != n)) {
permSub(n + 1, remove(x, xs), x::ys)
}
}
}
//
permSub(1, (1 to n).toList, Nil)
}
derangement は簡単です。実際の処理は局所関数 permSub で行います。引数 n が順番を表します。引数 ys は累積変数として使います。for 式の中で、数字 x が n と等しくない場合、その数字を選択することできます。等しい場合は選択しません。xs が空リストになったら、reverse で ys を反転して関数 f を呼び出します。これで完全順列を生成することができます。
結果をリストに格納する場合は次のようになります。
リスト : 完全順列 (2)
def derangement1(n: Int): List2[Int] = {
def permSub(n: Int, xs: List[Int], ys: List[Int], zs: List2[Int]): List2[Int] = {
xs match {
case Nil => ys.reverse :: zs
case _ => xs.foldLeft(zs)((a, x) => if (x != n) permSub(n + 1, remove(x, xs), x::ys, a) else a)
}
}
//
permSub(1, (1 to n).toList, Nil, Nil)
}
局所関数 permSub に累積変数 zs を追加します。xs が空リストになったら ys を zs に追加します。そうでなければ、メソッド foldLeft を呼び出して、x が n と等しくなければ x を選んで permSub を再帰呼び出しします。そうでなければ、引数 a をそのまま返します。
簡単な実行例を示します。
scala> derangement1(3) val res0: yasp03.List2[Int] = List(List(3, 1, 2), List(2, 3, 1)) scala> derangement1(4).foreach(println) List(4, 3, 2, 1) List(4, 3, 1, 2) List(4, 1, 2, 3) List(3, 4, 2, 1) List(3, 4, 1, 2) List(3, 1, 4, 2) List(2, 4, 1, 3) List(2, 3, 4, 1) List(2, 1, 4, 3)
リスト : 完全順列の総数
def montmortNumber(n: Int): BigInt =
n match {
case 1 => 0
case 2 => 1
case _ => (n - 1) * (montmortNumber(n - 1) + montmortNumber(n - 2))
}
// 別解
def montmortNumber1(n: Int): BigInt = {
def iter(i: Int, a: BigInt, b: BigInt): BigInt =
if (n == i) a
else iter(i + 1, b, (i + 1) * (a + b))
//
iter(1, 0, 1)
}
関数 montmortNumber は公式をそのままプログラムしただけです。二重再帰になっているので、実行速度はとても遅くなります。これを繰り返しに変換すると別解のようになります。考え方はフィボナッチ数列と同じです。累積変数 a に i 番目の値を、b に i + 1 番目の値を保存しておきます。すると、i + 2 番目の値は (i + 1) * (a + b) で計算することができます。あとは、b の値を a に、新しい値を b にセットして処理を繰り返すだけです。
リスト : カッコ列の生成
def kakko(f: String => Unit, n: Int): Unit = {
def iter(x: Int, y: Int, a: String): Unit = {
if (x == n && y == n) f(a)
else {
if (x < n) iter(x + 1, y, a + "(")
if (y < x) iter(x, y + 1, a + ")")
}
}
//
iter(0, 0, "")
}
カッコ列の生成は簡単です。局所関数 iter の引数 x が左カッコの個数、引数 y が右カッコの個数を表します。引数 a はカッコ列 (文字列) を格納する累積変数です。
バランスの取れたカッコ列の場合、x, y, m には y <= x <= m の関係が成り立ちます。x == m かつ y == m の場合、カッコ列がひとつ完成しました。f(a) を呼び出します。そうでなければ、iter を再帰呼び出しします。x < m であれば左カッコを追加し、y < x であれば右カッコを追加します。これでカッコ列を生成することができます。
結果をプログラムに格納する場合は次のようになります。
リスト : カッコ列の生成 (2)
def kakko1(n: Int): List[String] = {
def iter(x: Int, y: Int, a: String, b: List[String]): List[String] = {
if (x == n && y == n) a :: b
else {
val b1 = if (x < n) iter(x + 1, y, a + "(", b) else b
if (y < x) iter(x, y + 1, a + ")", b1) else b1
}
}
//
iter(0, 0, "", Nil)
}
局所関数 iter に累積変数 b を追加します。カッコ列がひとつ完成したら、a を b に追加して返すだけです。
簡単な実行例を示します。
scala> kakko1(3) val res0: List[String] = List(()()(), ()(()), (())(), (()()), ((()))) scala> kakko1(4).foreach(println) ()()()() ()()(()) ()(())() ()(()()) ()((())) (())()() (())(()) (()())() (()()()) (()(())) ((()))() ((())()) ((()())) (((())))
カタラン数 - Wikipedia によると、カッコ列の総数は「カタラン数 (Catalan number)」になるとのことです。カタラン数は次に示す公式で求めることができます。
これをそのままプログラムしてもいいのですが、それではちょっと面白くないので別な方法でプログラムを作ってみましょう。カタラン数は次に示す経路図において、A から B までの最短距離の道順を求めるとき、対角線を超えないものの総数に一致します。
Ｂ Ｂ
┌─┬─┬─┬─┐ ┌─┬─┬─０─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─┼─０─５─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─０─２─５─９
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ０─１─２─３─４
│ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┘ １─１─１─１─１
Ａ Ａ
図 : 道順の総数の求め方
A からある地点にいたる最短距離の道順の総数は、左隣と真下の地点の値を足したものになります。一番下の地点は 1 で、対角線を越えた地点は 0 になります。あとは下から順番に足し算していけば、A から B までの道順の総数を求めることができます。上図の場合はカラタン数 Ｃ4 に相当し、その値は 14 となります。
これをそのままプログラムすると、次のようになります。
リスト : カッコ列の総数
def kakkoNum(m: Int): BigInt = {
def iter(xs: List[BigInt]): BigInt =
xs match {
case Nil => throw new Exception("kakkoNum: Empty List")
case x::Nil => x
case _::ys => {
val zs = ys.foldLeft(List(0: BigInt))((b, x) => (x + b.head)::b)
iter(zs.reverse.tail)
}
}
//
iter(List.fill(m + 1)(1: BigInt))
}
実際の処理は局所関数 iter で行います。最初に List.fill で一番下の地点の道順の総数 (1) を格納したリスト生成します。これが iter に渡す初期値になります。引数 m のカラタン数を求める場合、リストの大きさは m + 1 になります。あとは、リストの要素がひとつになるまで iter を再帰呼び出しします。
一段上の地点の値を求める場合、畳み込み foldLeft を使うと簡単です。初期値はリスト [0] とします。これが対角線を越えた地点の値を表します。引数の先頭要素は不要なので、パターン _::xs で分解して foldLeft に渡します。匿名関数の引数 x が真下の地点の値、引数 b の先頭要素が左隣の地点の値になります。
あとは x と b.head を足し算して、それを演算子 :: でリスト b の先頭に追加すればいいわけです。この場合、foldLeft が返すリストは逆順になるので、reverse で反転してから tail で先頭要素 (対角線を越えた地点の値) を削除します。これでカッコ列の総数 (カタラン数) を求めることができます。
//
// yasp03.scala : Yet Another Scala Problems (3)
//
// Copyright (C) 2014-2024 Makoto Hiroi
//
object yasp03 {
// Q21
def zipWith[A, B, C](f: (A, B) => C)(xs: List[A], ys: List[B]): List[C] =
(xs, ys) match {
case (Nil, _) | (_, Nil) => Nil
case (x::xs1, y::ys1) => f(x, y) :: zipWith(f)(xs1, ys1)
}
def zipWith1[A, B, C](f: (A, B) => C)(xs: List[A], ys: List[B]): List[C] =
for ((x, y) <- (xs zip ys)) yield f(x, y)
// Q22
def foldl2[A, B, C](f: (A, B, C) => A)(a: A)(xs: List[B], ys: List[C]): A =
(xs, ys) match {
case (Nil, _) | (_, Nil) => a
case (x::xs1, y::ys1) => foldl2(f)(f(a,x,y))(xs1, ys1)
}
def foldr2[A, B, C](f: (A, B, C) => C)(a: C)(xs: List[A], ys: List[B]): C =
(xs, ys) match {
case (Nil, _) | (_, Nil) => a
case (x::xs1, y::ys1) => f(x, y, foldr2(f)(a)(xs1, ys1))
}
type List2[A] = List[List[A]]
type List3[A] = List[List[List[A]]]
// Q23
def partitionNumber(n: Int): BigInt = {
def partNum(n: Int, k: Int): BigInt =
(n, k) match {
case (0, _) | (1, _) | (_, 1) => 1
case _ => if (n < 0 || k < 1) 0
else partNum(n - k, k) + partNum(n, k - 1)
}
//
partNum(n, n)
}
//
def partitionNumber1(n: Int): BigInt = {
val table = Array.fill(n + 1)(1: BigInt)
for (k <- 2 to n) {
for (m <- k to n) table(m) += table(m - k)
}
table(n)
}
// Q24
def partitionOfInt(f: List[Int] => Unit, n: Int): Unit = {
def partInt(n: Int, k: Int, xs: List[Int]): Unit = {
(n, k) match {
case (0, _) => f(xs.reverse)
case (1, _) => f((1::xs).reverse)
case (_, 1) => f((List.fill(n)(1) ++ xs).reverse)
case _ => {
partInt(n, k - 1, xs)
if (n - k >= 0) partInt(n - k, k, k::xs)
}
}
}
partInt(n, n, Nil)
}
def partitionOfInt1(n: Int): List2[Int] = {
def partInt(n: Int, k: Int, xs: List[Int], ys: List2[Int]): List2[Int] =
(n, k) match {
case (0, _) => (xs.reverse)::ys
case (1, _) => ((1::xs).reverse)::ys
case (_, 1) => ((List.fill(n)(1) ++ xs).reverse)::ys
case _ => {
val zs = partInt(n, k - 1, xs, ys)
if (n - k >= 0) partInt(n - k, k, k::xs, zs) else zs
}
}
//
partInt(n, n, Nil, Nil)
}
// Q25
def remove[A](x: A, xs: List[A]): List[A] =
xs match {
case Nil => Nil
case y::ys => if (x == y) ys else y :: remove(x, ys)
}
def partitionOfSet[A](f: List2[A] => Unit, xs: List[A]): Unit = {
def partSet(xs: List[A], ys: List2[A]): Unit =
xs match {
case Nil => f(ys)
case x::xs1 => {
partSet(xs1, List(x)::ys)
for (y <- ys) partSet(xs1, (x::y)::remove(y, ys))
}
}
//
partSet(xs.reverse, Nil)
}
def partitionOfSet1[A](xs: List[A]): List3[A] = {
def partSet(xs: List[A], ys: List2[A], zs: List3[A]): List3[A] =
xs match {
case Nil => ys::zs
case x::xs1 => {
val b = partSet(xs1, List(x)::ys, zs)
ys.foldRight(b)((y: List[A], a: List3[A]) => partSet(xs1, (x::y)::remove(y, ys), a))
}
}
//
partSet(xs.reverse, Nil, Nil)
}
// Q26
def combNum(n: Int, r: Int): BigInt =
if (n == r || r == 0) 1
else combNum(n, r - 1) * (n - r + 1) / r
def bellNumber(n: Int): BigInt = {
def iter(i: Int, xs: List[BigInt]): BigInt =
if (n == i) xs.head
else {
val ys = (for (k <- 0 to i) yield combNum(i, k)).toList
iter(i + 1, zipWith((_: BigInt) * (_: BigInt))(xs, ys).sum :: xs)
}
//
iter(0, List(1))
}
// Q27
def derangement(f: List[Int] => Unit, n: Int): Unit = {
def permSub(n: Int, xs: List[Int], ys: List[Int]): Unit = {
xs match {
case Nil => f(ys.reverse)
case _ => for (x <- xs if (x != n)) {
permSub(n + 1, remove(x, xs), x::ys)
}
}
}
//
permSub(1, (1 to n).toList, Nil)
}
def derangement1(n: Int): List2[Int] = {
def permSub(n: Int, xs: List[Int], ys: List[Int], zs: List2[Int]): List2[Int] = {
xs match {
case Nil => ys.reverse :: zs
case _ => xs.foldLeft(zs)((a, x) => if (x != n) permSub(n + 1, remove(x, xs), x::ys, a) else a)
}
}
//
permSub(1, (1 to n).toList, Nil, Nil)
}
// Q28
def montmortNumber(n: Int): BigInt =
n match {
case 1 => 0
case 2 => 1
case _ => (n - 1) * (montmortNumber(n - 1) + montmortNumber(n - 2))
}
def montmortNumber1(n: Int): BigInt = {
def iter(i: Int, a: BigInt, b: BigInt): BigInt =
if (n == i) a
else iter(i + 1, b, (i + 1) * (a + b))
//
iter(1, 0, 1)
}
// Q29
def kakko(f: String => Unit, n: Int): Unit = {
def iter(x: Int, y: Int, a: String): Unit = {
if (x == n && y == n) f(a)
else {
if (x < n) iter(x + 1, y, a + "(")
if (y < x) iter(x, y + 1, a + ")")
}
}
//
iter(0, 0, "")
}
def kakko1(n: Int): List[String] = {
def iter(x: Int, y: Int, a: String, b: List[String]): List[String] = {
if (x == n && y == n) a :: b
else {
val b1 = if (x < n) iter(x + 1, y, a + "(", b) else b
if (y < x) iter(x, y + 1, a + ")", b1) else b1
}
}
//
iter(0, 0, "", Nil)
}
//Q30
def kakkoNum(m: Int): BigInt = {
def iter(xs: List[BigInt]): BigInt =
xs match {
case Nil => throw new Exception("kakkoNum: Empty List")
case x::Nil => x
case _::ys => {
val zs = ys.foldLeft(List(0: BigInt))((b, x) => (x + b.head)::b)
iter(zs.reverse.tail)
}
}
//
iter(List.fill(m + 1)(1: BigInt))
}
}