挿入ソートはソート済みの配列に新しいデータを挿入していくことでソートします。最初は先頭のデータひとつがソート済みと考え、2 番目のデータをそこに挿入することからスタートします。データを挿入するので、そこにあるデータをどかさないといけません。そこで、挿入位置を決めるため後ろから順番に比較するとき、いっしょにデータの移動も行うことにします。
[9] 5 3 7 6 4 8 5 を取り出す
[9] * 3 7 6 4 8 5 を[9]の中に挿入する
[5 9] 3 7 6 4 8 9 をひとつずらして先頭に 5 を挿入
[5 9] * 7 6 4 8 3 を取り出して[5 9]の中に挿入する
[3 5 9] 7 6 4 8 先頭に 3 を挿入
[3 5 9] * 6 4 8 7 を取り出して[3 5 9] に挿入
[3 5 7 9] 6 4 8 9 を動かして 7 を挿入
残りの要素も同様に行う
図 : 挿入ソート
配列を挿入ソートする関数 insertSort を定義してください。
def insertSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit
scala> val a = Array(5, 6, 4, 7, 3, 8, 2, 9, 1, 0) val a: Array[Int] = Array(5, 6, 4, 7, 3, 8, 2, 9, 1, 0) scala> insertSort(a) scala> a val res1: Array[Int] = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
シェルソート (shell sort) は挿入ソートの改良版ともいえる方法です。最初は遠く離れた要素間でソートを開始し、徐々に間隔を狭めていきます。最後は隣り合った要素間でソートします。つまり、単純挿入ソートと同じになります。
9 5 3 7 6 4 2 8 最初の状態
9 6 間隔を 4 で分割する
5 4
3 8
7 2
6 9 各群をソートする
4 5
3 8
2 7
6 3 9 8 間隔を 2 で分割する
4 2 5 7
3 6 8 9 各群をソートする
2 4 5 7
3 2 6 4 8 5 9 7 間隔を 1 で分割する（単純挿入ソートと同じ）
2 3 4 5 6 7 8 9 ソート完了
図 : シェルソート
間隔が大きいときは要素の個数が少ないので、単純なアルゴリズムでもソートにかかる時間は少なくてすみます。間隔が小さくなると要素の個数は多くなりますが、大まかにソートされているので挿入ソートでも高速にソートすることが可能です。
配列をシェルソートする関数 shellSort を定義してください。
def shellSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit
scala> val a = Array(5, 6, 4, 7, 3, 8, 2, 9, 1, 0) val a: Array[Int] = Array(5, 6, 4, 7, 3, 8, 2, 9, 1, 0) scala> shellSort(a) scala> a val res3: Array[Int] = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。2 つに分けた各々の区間を同様に分割して 2 つの区間に分けます。最後は区間の要素がひとつになってソートが完了します。
9 5 3 7 6 4 2 8 最初の状態
9 5 3 7 6 4 2 8 7 を枢軸にして左側から 7 以上の値を探し、
L R 右側から 7 以下の値を探す。
2 5 3 7 6 4 9 8 交換する
L R
2 5 3 7 6 4 9 8 検索する
L R
2 5 3 4 6 7 9 8 交換する
L R
2 5 3 4 6 7 9 8 検索する。R と L が交差したら分割終了。
R L
[2 5 3 4 6] [7 9 8] この 2 つの区間について再び同様な分割を行う
図 : クイックソート
基準になる値のことを「枢軸 (pivot)」といいます。枢軸は要素の中から適当な値を選びます。今回は中央にある要素を選ぶことにしましょう。上図を見てください。左側から枢軸 7 以上の要素を探し、左側から 7 以下の要素を探します。探索のときは枢軸が番兵の役割を果たすので、ソート範囲外の要素を探索することはありません。見つけたらお互いの要素を交換します。探索位置が交差したら分割は終了です。
あとは同じ手順を分割した 2 つの区間に適用します。これは再帰定義を使えば簡単に実現できます。分割した区間の要素数が 1 になったときが再帰の停止条件になります。
配列をクイックソートする関数 quickSort を定義してください。
def quickSort[A](buff: Array[A], low: Int, high: Int)(implicit f: A => Ordered[A]): Unit
scala> val a = Array(5, 6, 4, 7, 3, 8, 2, 9, 1, 0) val a: Array[Int] = Array(5, 6, 4, 7, 3, 8, 2, 9, 1, 0) scala> quickSort(a, 0, 9) scala> a val res5: Array[Int] = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
マージ (併合) とは、複数のソート済みのリストを一つのソート済みのリストにまとめる操作です。次の図を見てください。
┌─ [1, 3, 5] : リスト a
[] ←┤
└─ [2, 4, 6] : リスト b
小さい方をセットする
┌─ [3, 5] : リスト a
[1] ←┘
[2, 4, 6] : リスト b
1 をセットする
[3, 5] : リスト a
[1, 2] ←┐
└─ [4, 6] : リスト b
2 をセットする
データがなくなるまで繰り返す
図 : リストのマージ
2 つのリスト a と b があります。これらのリストはソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みのリストにまとめることができます。途中でどちらかのリストが空になったら、残ったリストのデータをそのまま追加します。
2 つのリストをマージする関数 mergeList を定義してください。
def mergeList[A](xs: List[A], ys: List[A])(implicit f: A => Ordered[A]): List[A]
scala> mergeList(List(1, 3, 5, 7, 9), List(2, 4, 6, 8)) val res6: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> mergeList(List(1, 3, 5, 7, 9), List(0, 2, 4, 6, 8)) val res7: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
マージソートはマージを使ってデータをソートします。次の図を見てください。
9 5 3 7 6 4 2 8 最初の状態
|5 9|3 7|4 6|2 8| 長さ２の列に併合
|3 5 7 9|2 4 6 8| 長さ４の列に併合
2 3 4 5 6 7 8 9 ソート終了
図 : マージソート
マージをソートに応用する場合、最初は各要素をソート済みのリストとして考えます。この状態で隣のリストとマージを行い、長さ 2 のリストを作ります。次に、このリストに対して再度マージを行い、長さ 4 のリストを作ります。このように順番にマージしていくと、最後にはひとつのリストにマージされソートが完了します。
実際にプログラムを作る場合、リストの長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単です。まず、ソートするリストを 2 つに分割して、前半部分をソートします。次に、後半部分をソートして、その結果をマージすればいいわけです。
再帰呼び出しするたびにリストは 2 つに分割されるので、最後にリストの要素はひとつとなります。これはソート済みのリストなので、ここで再帰呼び出しを終了してマージ処理を行えばいいわけです。
リストをマージソートする関数 mergeSort を定義してください。
def mergeSort[A](n: Int, xs: List[A])(implicit f: A => Ordered[A]): List[A]
scala> mergeSort(9, List(5, 6, 4, 7, 3, 8, 2, 9, 1)) val res8: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> mergeSort(9, List(9, 8, 7, 6, 5, 4, 3, 2, 1)) val res9: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> mergeSort(9, List(1, 2, 3, 4, 5, 6, 7, 8, 9)) val res10: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
リスト xs のべき集合を求める関数 powerSet を定義してください。たとえばリスト (1, 2, 3) のべき集合は Nil, (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3) になります。
def powerSet[A](xs: List[A]): List[List[A]]
scala> powerSet(List(1, 2, 3)).foreach(println) List() List(3) List(2) List(2, 3) List(1) List(1, 3) List(1, 2) List(1, 2, 3) scala> powerSet(List(1, 2, 3, 4)).foreach(println) List() List(4) List(3) List(3, 4) List(2) List(2, 4) List(2, 3) List(2, 3, 4) List(1) List(1, 4) List(1, 3) List(1, 3, 4) List(1, 2) List(1, 2, 4) List(1, 2, 3) List(1, 2, 3, 4)
リスト xs の中で連続した等しい記号を部分リストにまとめる関数 pack を定義してください。
def pack[A](xs: List[A]): List[List[A]]
scala> pack(List(1, 1, 1, 2, 3, 3, 4, 4, 4, 5)) val res11: List[List[Int]] = List(List(1, 1, 1), List(2), List(3, 3), List(4, 4, 4),List(5)) scala> pack(List(1, 2, 3, 1, 2, 3)) val res12: List[List[Int]] = List(List(1), List(2), List(3), List(1), List(2), List(3))
連続している同じ記号を (code . num) に変換する関数 encode と、その逆変換を行う関数 decode を定義してください。code は記号、num は個数を表します。このような変換を「ランレングス符号化」といいます。
def encode[A](xs: List[A]): List[(A, Int)] def decode[A](xs: List[(A, Int)]): List[A]
scala> encode(List(1, 1, 1, 2, 3, 3, 3, 3, 4, 4, 1, 1, 1, 5, 5, 5, 5, 5)) val res13: List[(Int, Int)] = List((1,3), (2,1), (3,4), (4,2), (1,3), (5,5)) scala> decode(encode(List(1, 1, 1, 2, 3, 3, 3, 3, 4, 4, 1, 1, 1, 5, 5, 5, 5, 5))) val res14: List[Int] = List(1, 1, 1, 2, 3, 3, 3, 3, 4, 4, 1, 1, 1, 5, 5, 5, 5, 5)
k 個の要素をもつ集合 ls を要素数が等しい m 個の部分集合に分割することを考えます。部分集合の要素数 n は k / m になります。分割の仕方をすべて求める高階関数 groupPartition を定義してください。
type List2[A] = List[List[A]] def groupPartition[A](f: List2[A] => Unit, n: Int, m: Int, xs: List[A]): Unit
scala> groupPartition(println, 2, 2, List(1, 2, 3, 4)) List(List(1, 4), List(2, 3)) List(List(1, 3), List(2, 4)) List(List(1, 2), List(3, 4)) scala> groupPartition(println, 2, 3, List(1, 2, 3, 4, 5, 6)) List(List(1, 6), List(2, 5), List(3, 4)) List(List(1, 5), List(2, 6), List(3, 4)) List(List(1, 6), List(2, 4), List(3, 5)) List(List(1, 4), List(2, 6), List(3, 5)) List(List(1, 5), List(2, 4), List(3, 6)) List(List(1, 4), List(2, 5), List(3, 6)) List(List(1, 6), List(2, 3), List(4, 5)) List(List(1, 3), List(2, 6), List(4, 5)) List(List(1, 2), List(3, 6), List(4, 5)) List(List(1, 5), List(2, 3), List(4, 6)) List(List(1, 3), List(2, 5), List(4, 6)) List(List(1, 2), List(3, 5), List(4, 6)) List(List(1, 4), List(2, 3), List(5, 6)) List(List(1, 3), List(2, 4), List(5, 6)) List(List(1, 2), List(3, 4), List(5, 6))
集合を groupPartition で分割するとき、その仕方の総数を多倍長整数 (BigInt) で求める関数 groupPartitionNumber を定義してください。
def groupPartitionNumber(n: Int, m: Int): BigInt
引数 n は部分集合の要素数、m は部分集合の個数です。
scala> groupPartitionNumber(2, 2) val res15: BigInt = 3 scala> groupPartitionNumber(2, 3) val res16: BigInt = 15 scala> groupPartitionNumber(3, 5) val res17: BigInt = 1401400
リスト : 挿入ソート
def insertSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit = {
val k = buff.size
for (i <- 1 until k) {
val tmp = buff(i)
var j = i - 1
while (j >= 0 && tmp < buff(j)) {
buff(j + 1) = buff(j)
j -= 1
}
buff(j + 1) = tmp
}
}
最初のループで挿入するデータを選びます。ソート開始時は先頭のデータひとつがソート済みと考えるるので、2 番目のデータ（添字では 1）を取り出して挿入していきます。2 番目のループで挿入する位置を探しています。探索は後ろから前に向かって行います。このとき、挿入位置の検索と同時にデータの移動も行っています。ループが最後まで回れば、そのデータは先頭に挿入されることになります。
ところで、挿入ソートは興味深い特性をもっています。ソート済みのデータは高速にソートすることができます。データがソートされていれば、2 番目のループは繰り返しを行わずに終了するため、最初のループの繰り返し回数でソートが完了することになります。したがって、与えられたデータが大まかにでもソートされていれば、2 番目のループで繰り返す回数が少なくなり、挿入ソートでも高速にソートすることができます。
リスト : シェルソート
def shellSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit = {
val k = buff.size
var gap = k / 2
while (gap > 0) {
for (i <- gap until k) {
val tmp = buff(i)
var j = i - gap
while (j >= 0 && tmp < buff(j)) {
buff(j + gap) = buff(j)
j -= gap
}
buff(j + gap) = tmp
}
gap /= 2
}
}
最初のループで間隔を徐々に狭めていきます。ここでは単純に 2 で割っていくことにしました。次のループで比較する要素を取り出します。最後のループでこの要素を挿入する位置を探索します。このときの探索は隣り合った要素ではなく gap 離れた要素を比較します。
2 番目のループでは、各群を並列にソートしていることに注意してください。群のひとつの要素を取り出して位置を決めたら、次の群の要素を取り出して位置を決めています。最後に gap は 1 になるので、挿入ソートと同じになりソートが完了します。
ところで、gap を常に奇数になるようにすると、シェルソートの実行速度はデータの個数 n の 1.5 乗に比例します。また、Knuth によると、gap の値に次の数列を用いると、シェルソートは n の 1.25 乗に比例するそうです。
gap = ..., 121, 40, 13, 4, 1
この数列は 3 倍して 1 を加えることで得られる数列を逆にしたものです。これをプログラムすると、次のようになります。
リスト : シェルソートの改良版
def shellSort1[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit = {
val k = buff.size
var gap = 1
while (gap < k / 9) gap = gap * 3 + 1
while (gap > 0) {
for (i <- gap until k) {
val tmp = buff(i)
var j = i - gap
while (j >= 0 && tmp < buff(j)) {
buff(j + gap) = buff(j)
j -= gap
}
buff(j + gap) = tmp
}
gap /= 3
}
}
リスト : クイックソート
def quickSort[A](buff: Array[A], low: Int, high: Int)(implicit f: A => Ordered[A]): Unit = {
val p = buff(low + (high - low) / 2)
var i = low
var j = high
while (true) {
while (p > buff(i)) i += 1
while (p < buff(j)) j -= 1
if (i >= j) {
if (low < i - 1) quickSort(buff, low, i - 1)
if (high > j + 1) quickSort(buff, j + 1, high)
return
} else {
val tmp = buff(i)
buff(i) = buff(j)
buff(j) = tmp
i += 1
j -= 1
}
}
}
関数 quickSort の引数 buff がソートするリスト、low が区間の下限値、high が区間の上限値です。quickSort は buff の low から high までの区間をソートします。最初に、区間の中央にあるデータを枢軸として選びます。そして、最初の while ループで pivot を基準にして区間を 2 つに分けます。
次の while ループで、左側から枢軸以上の要素を探しています。ここでは枢軸以上という条件を、枢軸より小さい間は探索位置を進める、というように置き換えています。同様に次の while ループで右側から枢軸以下の要素を探します。お互いの探索位置 i, j が交差したら分割は終了です。そうでなければお互いの要素を交換します。交換したあとは i と j の値を更新しておくことを忘れないでください。
そして、分割した区間に対して quickSort を再帰呼び出しします。このとき要素数をチェックして、2 個以上ある場合に再帰呼び出しを行います。この停止条件を忘れると正常に動作しません。ご注意ください。
ところで、クイックソートは枢軸の選び方で効率が大きく左右されます。区間の中間値を枢軸に選ぶと、区間をほぼ半分に分割することができます。この場合がいちばん効率が良く、データ数を N とすると N * log N に比例する時間でソートすることができます。
逆に、区間での最大値または最小値を枢軸に選ぶと、その要素と残りの要素の 2 つに分割にされることになります。これが最悪の場合で、分割のたびに最大値もしくは最小値を選ぶと、実行時間は要素数の 2 乗に比例することになります。つまり、挿入ソートと同じくらい遅いソートになります。
リスト : リストのマージ
def mergeList[A](xs: List[A], ys: List[A])(implicit f: A => Ordered[A]): List[A] =
(xs, ys) match {
case (Nil, _) => ys
case (_, Nil) => xs
case (x::xs1, y::ys1) => if (x <= y) x::mergeList(xs1, ys)
else y::mergeList(xs, ys1)
}
関数 mergeList の引数 xs, ys がマージするリストです。最初の節はリスト xs が空リストになった場合で、リスト ys をそのまま返します。2 番目の節はリスト ys が空リストになった場合で、リスト xs をそのまま返します。この 2 つが再帰呼び出しの停止条件になります。
リスト xs と ys にデータがあれば、先頭要素 x と y を演算子 <= で比較します。返り値が真であれば x を、そうでなければ y を mergeList が返すリストに追加します。mergeList を再帰呼び出しするとき、追加する要素をリストから取り除くことに注意してください。これでリストをマージすることができます。
リスト : マージソート
def mergeSort[A](n: Int, xs: List[A])(implicit f: A => Ordered[A]): List[A] =
(n, xs) match {
case (_, Nil) => Nil
case (1, x::_) => List(x)
case (2, x::y::_) => if (x > y) List(y, x) else List(x, y)
case _ => {
val m = n / 2
mergeList(mergeSort(m, xs), mergeSort(n - m, xs.drop(m)))
}
}
関数 merge_sort の第 1 引数がリストの長さ、第 2 引数がソートするリストです。merge_sort はリストを分割する処理で、新しいリストを作らないことに注意してください。次の図を見てください。
引数 x
｜
｜←── 長さn ──→｜
（１ ２ ３ ４ ５ ６ ７ ８）
｜←n/2→｜ ｜←n/2→｜
｜ ｜
引数 x 引数 y 再帰呼び出し
図 : リストの分割
mergeSort はソートするリストの範囲を開始位置と長さで表しています。上図のリストを二分割する場合、前半部分は x と n / 2 で表し、後半部分を y と n / 2 で表します。y はリスト x の先頭から n / 2 個の要素を取り除けば求めることができます。
あとは再帰呼び出しでリストを分割していき、リストの長さが 1 になったならば新しいリストを返します。リストの長さが 2 の場合は簡単なので、2 つの要素を比較してソート済みのリストを作成して返します。そして、mergeSort の返り値を mergeList でマージすればいいわけです。
リストを二分割していくのではなく、要素が 1 つのリストを作って、それを順番にマージしていくこともできます。次のリストを見てください。
リスト : マージソート (別解)
def mergeSort1[A](xs: List[A])(implicit f: A => Ordered[A]): List[A] = {
def iter1(xs: List[List[A]]): List[A] =
xs match {
case x::Nil => x
case _ => iter1(iter2(xs))
}
def iter2(xs: List[List[A]]): List[List[A]] =
xs match {
case Nil => Nil
case x::Nil => xs
case x::y::zs => mergeList(x, y) :: iter2(zs)
}
iter1(xs.map(List(_)))
}
実際の処理は局所関数 iter1 と iter2 で行います。最初に、map で要素をリストに格納して、それを iter1 に渡します。iter1 はリストの要素がひとつになるまで、iter2 を繰り返し呼び出します。iter2 は先頭から順番にリストを 2 つ取り出して、それを mergeList でマージします。そして、その結果をリストに格納して返します。
簡単な実行例を示します。
scala> mergeSort1(List(5,6,4,7,3,8,2,9,1)) val res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> mergeSort1(List(9,8,7,6,5,4,3,2,1)) val res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> mergeSort1(List(1,2,3,4,5,6,7,8,9)) val res2: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
リスト : べき集合
def powerSet[A](xs: List[A]): List[List[A]] =
xs match {
case Nil => List(Nil)
case x::xs1 => {
val ys = powerSet(xs1)
ys ::: ys.map(x::_)
}
}
// 別解
def powerSet1[A](f: List[A] => Unit, xs: List[A]): Unit = {
def iter(xs: List[A], a: List[A]): Unit = {
xs match {
case Nil => f(a.reverse)
case x::xs1 => { iter(xs1, a); iter(xs1, x::a) }
}
}
iter(xs, Nil)
}
べき集合を求める関数 power-set は簡単です。xs が空リストの場合は Nil を格納したリストを返します。そうでなければ powerSet を再帰呼び出しして xs1 のべき集合を求め、その集合に先頭要素 x を追加します。そして、その集合と xs1 のべき集合を演算子 ::: で連結します。
別解の powerSet1 は高階関数バージョンです。リストの長さを N とすると、べき集合の要素数は 2 ^ N になります。N が大きくなると、べき集合をリストに格納して返すことは困難になります。その場合は高階関数を使うとよいでしょう。
簡単な実行例を示します。
scala> powerSet1(println, List(1,2,3)) List() List(3) List(2) List(2, 3) List(1) List(1, 3) List(1, 2) List(1, 2, 3) scala> powerSet1(println, List(1,2,3,4)) List() List(4) List(3) List(3, 4) List(2) List(2, 4) List(2, 3) List(2, 3, 4) List(1) List(1, 4) List(1, 3) List(1, 3, 4) List(1, 2) List(1, 2, 4) List(1, 2, 3) List(1, 2, 3, 4)
リスト : 連続した同じ記号を部分リストにまとめる
def pack[A](xs: List[A]): List[List[A]] =
xs match {
case Nil => Nil
case _ => {
val (ys, zs) = xs.span(_ == xs.head)
ys :: pack(zs)
}
}
pack はリストを分割するメソッド span を使うと簡単です。引数 xs が空リストならば Nil を返します。そうでなければ span で先頭要素 xs.head と等しい要素のリスト ys と、残りのリスト xs に分割します。あとは、pack(zs) の返り値に ys を追加するだけです。
リスト : ランレングス符号化
def encode[A](xs: List[A]): List[(A, Int)] =
pack(xs).map(ys => (ys.head, ys.length))
def decode[A](xs: List[(A, Int)]): List[A] =
xs.flatMap(x => List.fill(x._2)(x._1))
// 別解
def encode1[A](xs: List[A]): List[(A, Int)] =
for ((y::ys) <- pack(xs)) yield (y, ys.length + 1)
def decode1[A](xs: List[(A, Int)]): List[A] =
for ((x, k) <- xs; y <- List.fill(k)(x)) yield y
encode は pack を使うと簡単です。pack の返り値を map で (code, n) に変換するだけです。ランレングスの復号は関数 flatmap と List.fill を使うと簡単です。List.fill で (code, n) をリストに変換し、flatmap でそれを平坦化するだけです。別解は for 内包表記で書き直したものです。
リスト : 集合のグループ分け
type List2[A] = List[List[A]]
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 groupPartition[A](f: List2[A] => Unit, n: Int, m: Int, xs: List[A]): Unit = {
def groupPart(xs: List[A], ys: List2[A]): Unit =
xs match {
case Nil => f(ys)
case x::xs1 => {
if (ys.length < m) groupPart(xs1, List(x)::ys)
for (y <- ys if (y.length < n)) groupPart(xs1, (x::y)::remove(y, ys))
}
}
//
groupPart(xs.reverse, Nil)
}
groupPartition は partitionOfSet (問題 25) を改造するだけで簡単に作成することができます。生成する部分集合の大きさを n に、部分集合の個数を m に制限するだけです。新しい部分集合 List(x) を追加する場合、ys.length < m であることをチェックします。部分集合 y に x を追加する場合、y.length < n であることをチェックします。これで集合をグループに分けることができます。
グループ分けの総数は次の式で求めることができます。
たとえば、n = 3, m = 5 の場合は次のようになります。
これをそのままプログラムすると次のようになります。
リスト : グループ分けの総数
def fact(n: Int): BigInt =
if (n == 0) 1
else n * fact(n - 1)
def combNum(n: Int, r: Int): BigInt =
if (n == r || r == 0) 1
else combNum(n, r - 1) * (n - r + 1) / r
def groupPartitionNumber(n: Int, m: Int): BigInt = {
def groupPartNum(k: Int, a: BigInt): BigInt =
if (k == 0) a / fact(m)
else groupPartNum(k - n, a * combNum(k, n))
groupPartNum(n * m, 1)
}
階乗は関数 fact で、組み合わせの個数は関数 combNum で計算します。要素の個数を変数 k にセットし、累積変数 a に combNum(k, n) を乗算します。あとは k から n を減算し、k が 0 でなければ処理を繰り返すだけです。最後に a / fact(m) を計算して返します。
//
// yasp05.scala : Yet Another Scala Problems
//
// Copyright (C) 2014-2024 Makoto Hiroi
//
import scala.math.Ordered.orderingToOrdered
object yasp05 {
// Q41
def insertSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit = {
val k = buff.size
for (i <- 1 until k) {
val tmp = buff(i)
var j = i - 1
while (j >= 0 && tmp < buff(j)) {
buff(j + 1) = buff(j)
j -= 1
}
buff(j + 1) = tmp
}
}
// Q42
def shellSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit = {
val k = buff.size
var gap = k / 2
while (gap > 0) {
for (i <- gap until k) {
val tmp = buff(i)
var j = i - gap
while (j >= 0 && tmp < buff(j)) {
buff(j + gap) = buff(j)
j -= gap
}
buff(j + gap) = tmp
}
gap /= 2
}
}
def shellSort1[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit = {
val k = buff.size
var gap = 1
while (gap < k / 9) gap = gap * 3 + 1
while (gap > 0) {
for (i <- gap until k) {
val tmp = buff(i)
var j = i - gap
while (j >= 0 && tmp < buff(j)) {
buff(j + gap) = buff(j)
j -= gap
}
buff(j + gap) = tmp
}
gap /= 3
}
}
// Q43
def quickSort[A](buff: Array[A], low: Int, high: Int)(implicit f: A => Ordered[A]): Unit = {
val p = buff(low + (high - low) / 2)
var i = low
var j = high
while (true) {
while (p > buff(i)) i += 1
while (p < buff(j)) j -= 1
if (i >= j) {
if (low < i - 1) quickSort(buff, low, i - 1)
if (high > j + 1) quickSort(buff, j + 1, high)
return
} else {
val tmp = buff(i)
buff(i) = buff(j)
buff(j) = tmp
i += 1
j -= 1
}
}
}
// Q44
def mergeList[A](xs: List[A], ys: List[A])(implicit f: A => Ordered[A]): List[A] =
(xs, ys) match {
case (Nil, _) => ys
case (_, Nil) => xs
case (x::xs1, y::ys1) => if (x <= y) x::mergeList(xs1, ys)
else y::mergeList(xs, ys1)
}
// Q45
def mergeSort[A](n: Int, xs: List[A])(implicit f: A => Ordered[A]): List[A] =
(n, xs) match {
case (_, Nil) => Nil
case (1, x::_) => List(x)
case (2, x::y::_) => if (x > y) List(y, x) else List(x, y)
case _ => {
val m = n / 2
mergeList(mergeSort(m, xs), mergeSort(n - m, xs.drop(m)))
}
}
// 別解
def mergeSort1[A](xs: List[A])(implicit f: A => Ordered[A]): List[A] = {
def iter1(xs: List[List[A]]): List[A] =
xs match {
case x::Nil => x
case _ => iter1(iter2(xs))
}
def iter2(xs: List[List[A]]): List[List[A]] =
xs match {
case Nil => Nil
case x::Nil => xs
case x::y::zs => mergeList(x, y) :: iter2(zs)
}
iter1(xs.map(List(_)))
}
// Q46
def powerSet[A](xs: List[A]): List[List[A]] =
xs match {
case Nil => List(Nil)
case x::xs1 => {
val ys = powerSet(xs1)
ys ::: ys.map(x::_)
}
}
// 別解 (高階関数)
def powerSet1[A](f: List[A] => Unit, xs: List[A]): Unit = {
def iter(xs: List[A], a: List[A]): Unit = {
xs match {
case Nil => f(a.reverse)
case x::xs1 => { iter(xs1, a); iter(xs1, x::a) }
}
}
iter(xs, Nil)
}
// Q47
def pack[A](xs: List[A]): List[List[A]] =
xs match {
case Nil => Nil
case _ => {
val (ys, zs) = xs.span(_ == xs.head)
ys :: pack(zs)
}
}
// Q48
def encode[A](xs: List[A]): List[(A, Int)] =
pack(xs).map(ys => (ys.head, ys.length))
def decode[A](xs: List[(A, Int)]): List[A] =
xs.flatMap(x => List.fill(x._2)(x._1))
def encode1[A](xs: List[A]): List[(A, Int)] =
for ((y::ys) <- pack(xs)) yield (y, ys.length + 1)
def decode1[A](xs: List[(A, Int)]): List[A] =
for ((x, k) <- xs; y <- List.fill(k)(x)) yield y
// Q49
type List2[A] = List[List[A]]
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 groupPartition[A](f: List2[A] => Unit, n: Int, m: Int, xs: List[A]): Unit = {
def groupPart(xs: List[A], ys: List2[A]): Unit =
xs match {
case Nil => f(ys)
case x::xs1 => {
if (ys.length < m) groupPart(xs1, List(x)::ys)
for (y <- ys if (y.length < n)) groupPart(xs1, (x::y)::remove(y, ys))
}
}
//
groupPart(xs.reverse, Nil)
}
// Q50
def fact(n: Int): BigInt =
if (n == 0) 1
else n * fact(n - 1)
def combNum(n: Int, r: Int): BigInt =
if (n == r || r == 0) 1
else combNum(n, r - 1) * (n - r + 1) / r
def groupPartitionNumber(n: Int, m: Int): BigInt = {
def groupPartNum(k: Int, a: BigInt): BigInt =
if (k == 0) a / fact(m)
else groupPartNum(k - n, a * combNum(k, n))
groupPartNum(n * m, 1)
}
}