前回は順列を生成するクラスを作成しました。nPkの公式を知っていれば、順列の数がどれだけなのか計算が出来ます。しかし、順列を全て列挙するというのは、人の手によると大変な作業です。nがちょっと大きくなるとすぐに手に負えなくなります。コンピュータのありがたさがわかるシーンです。今回は組合せを生成するクラスを作ってみましょう。前回作成したPermutationクラスを活用して、出来るだけシンプルなクラスにしましょう。2つのクラスに共通するクラスを抽出すれば更にシンプルなコードになるのですが、今回はそこまで要求しません。Permutationクラスをそのまま利用してください。
問題2 「n個の数値からk個を取る組合せ」を全て列挙するプログラムを作りましょう。
1からnまでの整数からk個取り出す場合を考えましょう。そして、取り得る場合を全て作成し、画面に出力するプログラムを作りましょう。組合せを作成するのは、順列のように簡単ではありません。重複する場合を取り除かなければならないからです。高速に処理する方法、メモリやディスクの使用量を抑える方法など様々考えられますが、今回は地味でも遅くてもかまいませんから、最もシンプルな方法で作成しましょう。
出力の形式は
- カウント:1番目の数値,2番目の数値,・・・,k番目の数値
としましょう。
組合せを生成するクラスはCombinationという名前にします。以下にスケルトンを示します。正しく処理するためのコードを追加して完成させましょう。
完成したCombination クラスを利用して、次のコードを動作させましょう。このソースコードを変更する必要はありません。このままで、Combination クラスを利用してください。
TestCombination.java の実行結果は次のようになるはずです。
解説
それでは、目的の動作をするコードの完成版を示します。Permutationクラスで順列を生成し、その中からユニークな組合せをピックアップしていく仕組みです。何の工夫もない、いたって単純な方法です。順列は大変大きな数になりやすいので、ユニークな要素のピックアップには工夫のしどころが多くあります。発展課題として取り組んでみてはいかがでしょうか。
今回はここまで
Permutationクラスを利用することで、Combinationクラスのコンストラクタはシンプルになりました。しかし、全体にわたってCombinationクラスのメソッドはPermutationクラスと共通しています。共通部分をスーパークラスに抽出し、より洗練された美しいコードを目指すのは、良い発展課題となるでしょう。
これで、確率の数学をコンピュータで学習するための道具がかなりそろいました。さいころ、そして順列と組合せのクラス。いろんなシミュレーションが出来そうですね。次回から、いよいよ本格的に確率の数学に取り組みます。お楽しみに。