順列と組み合わせ
今回は「順列 (permutation)」と「組み合わせ (combination)」を取り上げます。なお、Scala のライブラリには順列と組み合わせを求めるメソッドが用意されていますが、Scala のお勉強ということで、あえてプログラムを作ってみましょう。
●順列の生成
たとえば 4 つの整数 1, 2, 3, 4 の順列は次に示すように 24 通りあります。
1 2 3 4, 1 2 4 3, 1 3 2 4, 1 3 4 2, 1 4 2 3, 1 4 3 2 2 1 3 4, 2 1 4 3, 2 3 1 4, 2 3 4 1, 2 4 1 3, 2 4 3 1 3 1 2 4, 3 1 4 2, 3 2 1 4, 3 2 4 1, 3 4 1 2, 3 4 2 1 4 1 2 3, 4 1 3 2, 4 2 1 3, 4 2 3 1, 4 3 1 2, 4 3 2 1
一般に、異なる n 個の順列の総数は、n の階乗 (n!) 通りだけあります。この順列をすべて求めるプログラムを考えてみましょう。このときよく使われる方法に「バックトラック法 (backtracking)」があります。
たとえば、簡単な例として迷路を考えてみましょう。ある地点 A で道が左右に分かれているとします。ここで、左の道を選んで先へ進むと、行き止まりになってしまいました。この場合は A 地点まで戻って右の道へ進まないといけませんね。つまり、失敗したら後戻りして別の道を選ぶ、という試行錯誤をゴールに行き着くまで繰り返すわけです。これがバックトラック法の基本的な考え方です。
バックトラック法は迷路を解くだけではなく、いろいろな問題に応用できる方法です。とくに、すべての解を求める場合、バックトラック法が適しています。すべての解をもれなく見つけることができます。
順列は次のような図を書くと簡単に求めることができます。
上図は 1 から始まる場合です。同様に 2, 3, 4 から始まる図があります。最初が 1 であれば、次の数は 2, 3, 4 の中から選ばれますね。したがって、1 から 2, 3, 4 へと枝分かれします。1-2 と選んだ場合、次は 3, 4 の中から数を選びます。今度は 2 から 3, 4 へと枝分かれします。1-2-3 と選んだ場合は、残った数は 1 つしかありませんね。その数 4 を選んで 1-2-3-4 という並べ方が完成します。
ほかの並べ方を求めるには、今まで通った道を戻って別の道を探します。まず、1-2-3-4 から 1-2-3 まで後戻りします。この地点では 4 以外の道はないので、もうひとつ戻らなくてはいけません。1-2 まで戻ると、道は 2 つに枝分かれしています。3 はすでに通った道ですから、今度は 4 を選ぶことになります。この道を進んでいくと、1-2-4-3 という並べ方を求めることができます。
再度 1-2 まで後戻りします。2 つの道ともすでに通ったことがあるので、1 の位置まで後戻りします。この地点は 3 つに枝分かれしていますが、2 の道は通ったので今度は 3 を選んで 1-3 へ進みます。このように、通ったことがない道を選んでいき、1 から枝分かれする道をすべて通ったならば、START まで戻って 1 以外の道を選ぶことになります。あとは同様に道をたどっていけば、すべての並べ方を求めることができます。
●バックトラック法の実装
それでは、プログラムを作ってみます。ここまでの説明で、バックトラック法の実現は難しいのではないか、と思った方はいませんか。「進む」ことと「戻る」ことをどのようにプログラムしたらよいのか、見当もつかないという人もいるかもしれません。ところがバックトラック法は、今までに何回も使ってきた「再帰呼び出し」を利用すると、とても簡単に実現できるのです。
まず、「進む」場合を再帰呼び出しに対応させます。そうすると、ひとつ手前の位置に戻ることは、呼び出し元の関数に戻ることに対応させることができるのです。つまり、関数の評価を終了すれば、元の位置に「バックトラック」できるわけです。
具体的に説明しましょう。まず、順列を生成する関数を perm と定義します。perm の第 1 引数には選択していない数を格納したリストを渡し、第 2 引数には選んだ数を格納するリストを渡します。最初に呼び出すときは、次のようになります。
perm(List(1, 2, 3, 4), Nil)
まだ数を選択していないので、第 1 引数は (1, 2, 3, 4) となり、第 2 引数は Nil となります。数は第 1 引数のリストの中から選びます。再帰呼び出しする場合、選んだ数をリストから削除するとともに、第 2 引数のリストへ追加します。次の図を見てください。
最初はリスト (1, 2, 3, 4) の中から数を選びます。このとき、リストの先頭から順番に数を選んでいきます。最初は 1 を選びますが、バックトラックしたときは、次の 2 を選ぶようにします。再帰呼び出しするときは、第 1 引数のリストから 1 を削除し、それを第 2 引数のリストに追加します。数はリストの先頭へ追加していくので、並べ方が逆になることに注意してください。
このように、再帰呼び出しを続けていくと、第 1 引数は空リストになります。ここが、再帰呼び出しの停止条件となり、第 2 引数には数の並びが逆順にセットされています。これを出力すればいいわけです。
次に、新しい組み合わせを探すため、バックトラックを行います。次の図を見てください。
バックトラックすると、第 1 引数が (4) で第 2 引数が (3, 2, 1) の状態に戻ります。ここで、次の数を選ぶのですが、もうリストには数がありません。そこで、再度バックトラックします。すると、第 1 引数が (3, 4) で第 2 引数が (2, 1) の状態に戻ります。このときは、3 の次である 4 を選びます。第 1 引数 (3, 4) から 4 を取り除いた (3) と、第 2 引数 (2, 1) に 4 を追加した (4, 2, 1) を与えて再帰呼び出しします。あとは、同じことを繰り返すことで、順列をすべて求めることができるわけです。
●プログラムの作成
それでは、プログラムを示します。
リスト : 順列の生成
def permutation[A](xs: List[A]) = {
def perm(xs: List[A], a: List[A]): Unit =
xs match {
case Nil => println(a.reverse)
case _ => xs.foreach(x => perm(xs.filterNot(x == _), x::a))
}
perm(xs, Nil)
}
関数 permutation は局所関数 perm を呼び出します。引数 xs が数字を格納するリストで、引数 a に選んだ数字が格納されます。xs が空リストの場合、順列がひとつ完成したので、println で画面へ出力します。reverse でリストを反転していることに注意してください。
そうでなければ、第 1 引数のリストから数を順番に選んでいきます。この処理はメソッド foreach を使うと簡単です。foreach の繰り返しが終了すれば perm の評価も終了するので、選ぶ数がなくなったらバックトラックするという処理を実現することができます。foreach に渡す無名関数の中で perm を再帰呼び出しします。このとき、選んだ数字 x を filterNot で削除して、累積変数 a に追加します。
それでは実行してみましょう。
scala> permutation(List(1, 2, 3, 4)) List(1, 2, 3, 4) List(1, 2, 4, 3) List(1, 3, 2, 4) ・・省略・・ List(4, 2, 3, 1) List(4, 3, 1, 2) List(4, 3, 2, 1) scala> permutation(List(1, 2, 3)) List(1, 2, 3) List(1, 3, 2) List(2, 1, 3) List(2, 3, 1) List(3, 1, 2) List(3, 2, 1)
正常に動作していますね。
●高階関数版の作成
ところで、関数 permutation は順列を画面へ出力しましたが、高階関数にしたほうが便利でしょう。プログラムは次のようになります。
リスト : 順列の生成 (高階関数版)
def permutation0[A](f: List[A] => Unit, xs: List[A]) = {
def perm(xs: List[A], a: List[A]): Unit =
xs match {
case Nil => f(a.reverse)
case _ => xs.foreach(x => perm(xs.filterNot(x == _), x::a))
}
perm(xs, Nil)
}
関数 permutation0 の引数 f が関数で、xs がリストです。関数 f の型は List[A] => Unit になります。局所関数 perm は、順列を表示する処理を関数 f の呼び出しに変えただけです。あとは、perm を呼び出すだけです。とても簡単ですね。たとえば、引数 f に println を渡せば、順列をすべて表示することができます。
●リストの中から n 個の要素を選ぶ順列
リストの中から n 個の要素を選ぶ順列を生成することも簡単にできます。次のリストを見てください。
リスト : n 個の要素を選ぶ順列
def permutation1[A](f: List[A] => Unit, n: Int, xs: List[A]) = {
def perm(n: Int, xs: List[A], a: List[A]): Unit =
(n, xs) match {
case (0, _) => f(a.reverse)
case _ => xs.foreach(x => perm(n - 1, xs.filterNot(x == _), x::a))
}
perm(n, xs, Nil)
}
permutation1 の引数 n が選択する要素の個数です。局所関数 perm において、match 式で n と xs をタプルに格納してパターンマッチングします。n が 0 の場合は累積変数 a を逆順にして関数 f に渡します。あとのプログラムは今までと同じです。とても簡単ですね。
簡単な実行例を示します。
scala> permutation1(println, 2, List(1, 2, 3)) List(1, 2) List(1, 3) List(2, 1) List(2, 3) List(3, 1) List(3, 2) scala> permutation1(println, 2, List(1, 2, 3, 4)) List(1, 2) List(1, 3) List(1, 4) List(2, 1) List(2, 3) List(2, 4) List(3, 1) List(3, 2) List(3, 4) List(4, 1) List(4, 2) List(4, 3)
●順列をリストに格納する
生成した順列をリストに格納して返す場合は、畳み込みを行うメソッド foldRight を使うと簡単です。プログラムは次のようになります。
リスト : 順列の生成 (3)
def permutations[A](n: Int, xs: List[A]): List[List[A]] = {
def perm(n: Int, xs: List[A], a: List[A], b: List[List[A]]): List[List[A]] =
(n, xs) match {
case (0, _) => a.reverse :: b
case _ => xs.foldRight(b)((x, y) => perm(n - 1, xs.filterNot(x == _), x::a, y))
}
perm(n, xs, Nil, Nil)
}
局所関数 perm は生成した順列を引数 b のリストに格納して、それをそのまま返します。perm を呼び出す場合、この返り値を引数 b に渡すことで、生成した順列を格納していくことができます。ここで foldRight が役に立ちます。
foldRight の初期値を perm の引数 b にすることで、無名関数 (x y) => ... の引数 y に順列を格納するリストを渡します。あとは perm を再帰呼び出しすると、その返り値は次に無名関数 (x, y) => ... を呼び出すときの引数 y に渡されるので、順列を格納したリストを perm に渡していくことができます。
それでは実行結果を示します。
scala> permutations(4, List(1, 2, 3, 4)) val res4: List[List[Int]] = List( List(1, 2, 3, 4), List(1, 2, 4, 3), List(1, 3, 2, 4), List(1, 3, 4, 2), List(1, 4, 2, 3), List(1, 4, 3, 2), List(2, 1, 3, 4), List(2, 1, 4, 3), List(2, 3, 1, 4), List(2, 3, 4, 1), List(2, 4, 1, 3), List(2, 4, 3, 1), List(3, 1, 2, 4), List(3, 1, 4, 2), List(3, 2, 1, 4), List(3, 2, 4, 1), List(3, 4, 1, 2), List(3, 4, 2, 1), List(4, 1, 2, 3), List(4, 1, 3, 2), List(4, 2, 1, 3), List(4, 2, 3, 1), List(4, 3, 1, 2), List(4, 3, 2, 1))
●要素の選択
もうひとつ、順列を生成する簡単な方法を紹介しましょう。リストから要素を一つ選んで、選んだ要素と残りの要素を返す関数 select を定義すると、順列の生成は簡単にプログラムすることができます。次のリストを見てください。
リスト : 要素の選択
def select[A](xs: List[A]): List[(A, List[A])] =
xs match {
case Nil => throw new Exception("select: EmptyList")
case y::Nil => List((y, Nil))
case y::ys => (y, ys) :: (for ((z, zs) <- select(ys)) yield (z, y::zs))
}
select は選んだ要素と残りの要素をタプルに格納し、それをリストに格納して返します。最初の節で、xs が空リストの場合はエラーを送出します。Scala は Java と同様に例外処理をサポートしています。例外処理については回を改めて詳しく説明する予定です。次の節で、リストの要素が一つしかない場合は (y, Nil) をリストに格納して返します。これが再帰呼び出しの停止条件です。
最後の節で、リストを y :: ys で分解します。先頭要素 y を選ぶ場合は (y, ys) をリストに格納するだけです。それ以外の場合は、ys に対して select を再帰呼び出しし、返り値のタプルの第 2 要素 zs (残りの要素を格納したリスト) に y を追加します。この処理は for 内包表記を使うと簡単です。
それでは実行してみましょう。
scala> select(List(1, 2, 3)) val res5: List[(Int, List[Int])] = List((1,List(2, 3)), (2,List(1, 3)), (3,List(1, 2))) scala> select(List(1, 2, 3, 4)) val res6: List[(Int, List[Int])] = List((1,List(2, 3, 4)), (2,List(1, 3, 4)), (3,List(1, 2, 4)), (4,List(1, 2, 3)))
●順列をリストに格納する (2)
select を使うと順列を生成する関数 permutations は簡単にプログラムすることができます。まず、select で要素を一つ選び、残った要素で順列を生成します。これは再帰呼び出しを使えば簡単ですね。あとは生成した順列の先頭に、select で選んだ要素を追加すればいいのです。プログラムは次のようになります。
リスト : 順列をリストに格納する
def permutations1[A](n: Int, xs: List[A]): List[List[A]] =
(n, xs) match {
case (0, _) => List(Nil)
case _ => {
for ((y, ys) <- select(xs);
zs <- permutations1(n - 1, ys)) yield (y::zs)
}
}
最初の case 節で、n が 0 の場合は空リストを格納したリストを返します。これが再帰呼び出しの停止条件になります。次の節の for 内包表記で、xs から要素を一つ選びます。選んだ要素は y に、残りの要素は ys のリストに格納されます。それから、permutations1 に ys を渡して再帰呼び出しします。その返り値はリストで、その要素が順列になります。これを順番に取り出して変数 zs にセットします。あとは zs の先頭に y を追加して、それを yield でリストに挿入していくだけです。
それでは実行してみましょう。
scala> permutations1(3, List(1, 2, 3)) val res7: List[List[Int]] = List(List(1, 2, 3), List(1, 3, 2), List(2, 1, 3), List(2, 3, 1), List(3, 1, 2), List(3, 2, 1)) scala> permutations1(3, List(1, 2, 3, 4)) val res8: List[List[Int]] = List( List(1, 2, 3), List(1, 2, 4), List(1, 3, 2), List(1, 3, 4), List(1, 4, 2), List(1, 4, 3), List(2, 1, 3), List(2, 1, 4), List(2, 3, 1), List(2, 3, 4), List(2, 4, 1), List(2, 4, 3), List(3, 1, 2), List(3, 1, 4), List(3, 2, 1), List(3, 2, 4), List(3, 4, 1), List(3, 4, 2), List(4, 1, 2), List(4, 1, 3), List(4, 2, 1), List(4, 2, 3), List(4, 3, 1), List(4, 3, 2))
実は select を使わなくても、簡単に順列を生成することができます。次の例を見てください。
リスト : 順列の生成
def permutations2[A](n: Int, xs: List[A]): List[List[A]] =
(n, xs) match {
case (0, _) => List(Nil)
case _ => {
for (x <- xs;
ys <- permutations2(n - 1, xs.filterNot(x == _))) yield x::ys
}
}
引数 n が 0 の場合は空リストを格納したリストを返します。これが再帰呼び出しの停止条件になります。そうでなければ、for 内包表記でリスト xs の要素を順番に選んで変数 x にセットします。次に、xs から x を削除して、そのリストから n - 1 個の要素を選ぶ順列を生成します。これは permutatios2 を再帰呼び出しすれば簡単ですね。この返り値から要素 (順列) を順番に取り出して変数 ys にセットします。あとは、ys の先頭に x を追加して、yield でリストに挿入していけばいいわけです。興味のある方は実際に試してみてください。
●Scala の permutations
Scala のライブラリには順列を生成するメソッド permutations がありますが、それは「イテレータ」として定義されています。簡単な例を示しましょう。
scala> val iter = List(1,2,3).permutations val iter: Iterator[List[Int]] = <iterator> scala> iter.next() val res9: List[Int] = List(1, 2, 3) scala> iter.next() val res10: List[Int] = List(1, 3, 2) scala> iter.next() val res11: List[Int] = List(2, 1, 3) scala> iter.next() val res12: List[Int] = List(2, 3, 1) scala> iter.next() val res13: List[Int] = List(3, 1, 2) scala> iter.next() val res14: List[Int] = List(3, 2, 1) scala> iter.hasNext val res15: Boolean = false scala> val xs = List(1,2,3).permutations.toList val xs: List[List[Int]] = List(List(1, 2, 3), List(1, 3, 2), List(2, 1, 3), List(2, 3, 1), List(3, 1, 2), List(3, 2, 1))
イテレータにメソッド toList を適用すると、イテレータの要素をリストに格納して返すことができます。
●組み合わせの数
次は組み合わせの数を求めるプログラムを作ってみましょう。組み合わせの数 \({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。
皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。Scala は多倍長演算をサポートしているので、桁あふれを心配する必要はありません。
この公式をそのままプログラムすることもできますが、次の式を使うともっと簡単にプログラムできます。
この式は \({}_n \mathrm{C}_r\) と \({}_n \mathrm{C}_{r-1}\) の関係を表しています。あとは階乗と同じように、再帰定義を使って簡単にプログラムできます。次のリストを見てください。
リスト : 組み合わせの数を求める
def combNum(n: Int, r: Int): BigInt =
if (n == r || r == 0)
1
else
combNum(n, r - 1) * (n - r + 1) / r
scala> combNum(5, 3) val res0: BigInt = 10 scala> combNum(10, 5) val res1: BigInt = 252 scala> combNum(30, 15) val res2: BigInt = 155117520 scala> combNum(50, 25) val res3: BigInt = 126410606437752
●パスカルの三角形
それでは、関数 combNum を使って「パスカルの三角形」を作ってみましょう。次の図を見てください。
図 : パスカルの三角形
パスカルの三角形は、左側の図のように両側がすべて 1 で、内側の数はその左上と右上の和になっています。これは式 \((a + b)^n\) を展開したときの各項の係数を表しています。そして、その値は右側の図のように組み合わせの数 \({}_n \mathrm{C}_r\) に対応しています。
きれいな三角形にはなりませんが、簡単なプログラムを示します。
リスト : パスカルの三角形
def pascal(x: Int) = {
for (n <- 0 to x) {
for (r <- 0 to n) print(s"${combNum(n, r)} ")
println("")
}
}
for ループで二重ループを構成しています。最初の for ループで変数 n の値を 0 から x まで +1 ずつ増やし、次の for ループで変数 r の値を 0 から n まで +1 ずつ増やします。あとは combNum で \({}_n \mathrm{C}_r\) の値を計算するだけです。
実行結果は次のようになります。
scala> pascal(16) 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
次は関数 combNum を使わないでパスカルの三角形を出力するプログラムを作ってみましょう。パスカルの三角形は、両側がすべて 1 で内側の数はその左上と右上の和になっています。したがって、n 段の三角形を作る場合、一段前の値を記憶しておいて隣同士の要素を足し算すればいいわけです。一段前の値をリストに格納すると、プログラムは次のようになります。
リスト : パスカルの三角形 (2)
def pascal1(x: Int) = {
def next(xs: List[Int], a: List[Int]): List[Int] =
xs match {
case Nil => throw new Exception("pascal1: EmptyList")
case x::Nil => x :: a
case x::y::zs => next(y::zs, (x + y)::a)
}
var p = List(1)
println(p)
for (i <- 0 until x) {
p = next(p, List(1))
println(p)
}
}
関数 next は、リストの隣同士の要素を足した値をリストに格納して返します。引数 a が累積変数です。リスト xs が x::Nil とマッチングしたら、x を a の先頭に追加して a を返します。xs とパターン x::y::zs がマッチングしたら、先頭要素 x と次の要素 y を足し算し、それを a の先頭に追加して next を再帰呼び出しします。関数 pascal1 は for ループで next を x 回呼び出すだけです。
それでは実行してみましょう。
scala> pascal1(16) List(1) List(1, 1) List(1, 2, 1) List(1, 3, 3, 1) List(1, 4, 6, 4, 1) List(1, 5, 10, 10, 5, 1) List(1, 6, 15, 20, 15, 6, 1) List(1, 7, 21, 35, 35, 21, 7, 1) List(1, 8, 28, 56, 70, 56, 28, 8, 1) List(1, 9, 36, 84, 126, 126, 84, 36, 9, 1) List(1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1) List(1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1) List(1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1) List(1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1) List(1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1) List(1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1) List(1, 16, 120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1)
次は、配列を使ってプログラムを作ります。n 段の三角形を作る場合、大きさが n + 1 の配列を用意します。たとえば、6 段の三角形を作ってみましょう。次の図を見てください。
最初にベクタの内容を 1 に初期化します。n = 0, 1 の場合はこのままで大丈夫です。あとは図のように、隣の要素を足し算するだけです。プログラムは次のようになります。
リスト : パスカルの三角形 (3)
def pascal2(x :Int) = {
val table = new Array[Int](x + 1)
for (i <- 0 to x) table(i) = 1
println(table(0))
for (i <- 1 to x) {
for (j <- i - 1 until 0 by -1) {
table(j) += table(j - 1)
}
for (j <- 0 to i) print(s"${table(j)} ")
println("")
}
}
配列はひとつあれば十分です。ただし、配列の値を書き換えていくので、配列の後方から計算していくことに注意してください。前方から計算すると、値がおかしくなります。実行結果は次のようになります。
scala> pascal2(16) 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
●組み合わせの生成 (1)
今度は \({}_n \mathrm{C}_r\) 個の組み合わせを全て生成するプログラムを作ってみましょう。たとえば、1 から 5 までの数字の中から 3 個を選ぶ組み合わせは次のようになります。
(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)
最初に 1 を選択した場合、次は (2, 3, 4, 5) の中から 2 個を選べばいいですね。2 番目に 2 を選択したら、次は (3, 4, 5) の中から 1 個を選べばいいわけです。これで、(1, 2, 3), (1, 2, 4), (1, 2, 5) が生成されます。(2, 3, 4, 5) の中から 2 個選ぶとき、2 を選ばない場合があります。この場合は (3, 4, 5) の中から 2 個を選べばいいわけです。ここで 3 を選ぶと (1, 3, 4), (1, 3, 5) が生成できます。同様に、3 を除いた (4, 5) の中から 2 個を選ぶと (1, 4, 5) を生成することができます。
これで 1 を含む組み合わせを生成したので、次は 1 を含まない組み合わせ、つまり (2, 3, 4, 5) から 3 個を選ぶ組み合わせを生成すればいいわけです。けっきょく、この処理の考え方は次に示す組み合わせの公式と同じです。
Scala でプログラムを作ると次のようになります。
リスト : 組み合わせの生成
def combination[A](f: List[A] => Unit, n: Int, xs: List[A]) = {
def comb(n: Int, xs: List[A], a: List[A]): Unit = {
(n, xs) match {
case (0, _) => f(a.reverse)
case (_, Nil) => throw new Exception("combination: EmptyList")
case (_, y::ys) => {
if (xs.length == n)
f(a.reverse ::: xs)
else {
comb(n - 1, ys, y::a)
comb(n, ys, a)
}
}
}
}
comb(n, xs, Nil)
}
関数 combination は引数 xs のリストから n 個を選ぶ組み合わせを生成し、それを関数 f に渡して実行します。実際の処理は局所関数 comb で行います。選んだ数字は第 3 引数 a のリストに格納します。n が 0 になったら組み合わせを一つ生成できたので、a を reverse で逆順にして f を呼び出します。次の節で n が 0 ではなく、xs が空リストになった場合はエラーを送出します。
次の節で、リスト xs の長さが n と等しくなったならば、リストの要素を全て選択します。reverse で a を逆順にして演算子 ::: でリスト xs と結合してから f を呼び出します。あとは関数 comb を再帰呼び出しするだけです。最初の呼び出しは先頭の要素を選択する場合です。先頭要素 y を a に追加して、リスト ys の中から n - 1 個を選びます。最後の呼び出しが先頭の要素を選ばない場合です。リスト ys の中から n 個を選びます。
プログラムはこれで完成です。簡単な実行例を示しましょう。
scala> combination(println, 3, List(1, 2, 3, 4, 5)) List(1, 2, 3) List(1, 2, 4) List(1, 2, 5) List(1, 3, 4) List(1, 3, 5) List(1, 4, 5) List(2, 3, 4) List(2, 3, 5) List(2, 4, 5) List(3, 4, 5)
正常に動作していますね。
●組み合わせをリストに格納する
生成した組み合わせをリストに格納して返す場合も簡単です。プログラムは次のようになります。
リスト : 組み合わせの生成 (リストに格納)
def combinations[A](n: Int, xs: List[A]): List[List[A]] = {
def comb(n: Int, xs: List[A], a: List[A], b: List[List[A]]): List[List[A]] =
(n, xs) match {
case (0, _) => a.reverse :: b
case (_, Nil) => throw new Exception("combinations: EmptyList")
case (_, y::ys) => {
if (xs.length == n) (a.reverse ::: xs) :: b
else comb(n - 1, ys, y::a, comb(n, ys, a, b))
}
}
comb(n, xs, Nil, Nil)
}
局所関数 comb は、生成した組み合わせを引数 b のリストに格納し、それをそのまま返します。comb を呼び出す場合、この返り値を引数 b に渡すことで、生成した組み合わせを格納していくことができます。具体的には、comb を再帰呼び出しするところで、1 回目の呼び出しの返り値を 2 回目の呼び出しの第 4 引数に渡します。これで生成した組み合わせをリストに格納することができます。
それでは実行結果を示します。
scala> combinations(3, List(1, 2, 3, 4, 5)) val res1: List[List[Int]] = List( List(1, 2, 3), List(1, 2, 4), List(1, 2, 5), List(1, 3, 4), List(1, 3, 5), List(1, 4, 5), List(2, 3, 4), List(2, 3, 5), List(2, 4, 5), List(3, 4, 5))
●組み合わせをリストに格納する (2)
ところで、参考 URL には、もっと簡潔なプログラムが掲載されています。参考 URL のプログラムを Scala で書き直すと次のようになります。
リスト : 組み合わせの生成
def combinations1[A](n: Int, xs: List[A]): List[List[A]] =
(n, xs) match {
case (0, _) => List(Nil)
case (_, Nil) => Nil
case (_, y::ys) => combinations1(n - 1, ys).map(y::_) ::: combinations1(n, ys)
}
n が 0 になったら空リストを格納したリストを返します。リスト xs が y::ys とマッチングしたら、ys から n - 1 個の要素を選ぶ組み合わせを生成し、その先頭に y を追加します。これは combinations1 を再帰呼び出しして、map でリストの要素 (組み合わせ) に y を追加します。このリストと ys から n 個を選ぶ組み合わせを演算子 ::: で連結します。
プログラムのポイントは、引数のリストが空リストになったら、組み合わせを生成できないので空リストを返すところです。xs ::: Nil や Nil ::: xs は xs になるので、空リストを返しても正常に動作するわけです。とても参考になりました。山下伸夫さんに感謝いたします。
実行例を示します。
scala> combinations1(3, List(1,2,3,4,5)) val res2: List[List[Int]] = List(List(1, 2, 3), List(1, 2, 4), List(1, 2, 5), List(1, 3, 4), List(1, 3, 5), List(1, 4, 5), List(2, 3, 4), List(2, 3, 5), List(2, 4, 5), List(3, 4, 5))
●Scala の combinations
順列と同様に、Scala のライブラリには組み合わせを生成するメソッド combinations があり、それはイテレータとして定義されています。簡単な例を示します。
scala> val iter = List(1,2,3,4,5).combinations(3) val iter: Iterator[List[Int]] = <iterator> scala> iter.next() val res0: List[Int] = List(1, 2, 3) scala> iter.next() val res1: List[Int] = List(1, 2, 4) scala> iter.next() val res2: List[Int] = List(1, 2, 5) scala> iter.next() val res3: List[Int] = List(1, 3, 4) scala> iter.next() val res4: List[Int] = List(1, 3, 5) scala> List(1,2,3,4,5).combinations(3).toList val res5: List[List[Int]] = List(List(1, 2, 3), List(1, 2, 4), List(1, 2, 5), List(1, 3, 4), List(1, 3, 5), List(1, 4, 5), List(2, 3, 4), List(2, 3, 5), List(2, 4, 5), List(3, 4, 5))
●参考 URL
改訂 2021 年 4 月 4 日