はじめMath! Javaでコンピュータ数学

第50回 確率の数学 順列と組合せ [後編]

この記事を読むのに必要な時間:およそ 4 分

前回は順列を生成するクラスを作成しました。nPkの公式を知っていれば,順列の数がどれだけなのか計算が出来ます。しかし,順列を全て列挙するというのは,人の手によると大変な作業です。nがちょっと大きくなるとすぐに手に負えなくなります。コンピュータのありがたさがわかるシーンです。今回は組合せを生成するクラスを作ってみましょう。前回作成したPermutationクラスを活用して,出来るだけシンプルなクラスにしましょう。2つのクラスに共通するクラスを抽出すれば更にシンプルなコードになるのですが,今回はそこまで要求しません。Permutationクラスをそのまま利用してください。

問題2 「n個の数値からk個を取る組合せ」を全て列挙するプログラムを作りましょう。

1からnまでの整数からk個取り出す場合を考えましょう。そして,取り得る場合を全て作成し,画面に出力するプログラムを作りましょう。組合せを作成するのは,順列のように簡単ではありません。重複する場合を取り除かなければならないからです。高速に処理する方法,メモリやディスクの使用量を抑える方法など様々考えられますが,今回は地味でも遅くてもかまいませんから,最もシンプルな方法で作成しましょう。

出力の形式は

  • カウント:1番目の数値,2番目の数値,・,k番目の数値

としましょう。

組合せを生成するクラスはCombinationという名前にします。以下にスケルトンを示します。正しく処理するためのコードを追加して完成させましょう。

ソースコード:Combination.javaのスケルトン

/*
 * class Combination
 * 目的: 組合せに必要なメソッドを備える
 */

import java.util.ArrayList;

class Combination {

  //プライベートな変数・オブジェクトの宣言
  ArrayList _E = new ArrayList();
  int _n;
  int _k;

/*
 * 目的: コンストラクタ。組合せに必要な変数を用意し,
 * 組合せを作成する。
 * 引数: nCk のn,k
 */
  Combination(int n,int k){
    _n = n; _k = k;

    /*
      -------------------------------------------
      <手順>
     (1)Permutationクラスを利用して順列を作成する。
     (2)Permutationクラスで生成した順列を1つ1つ読み込む。
     (3)読み込んだ順列がユニークな組合せならば_Eに保持。
      -------------------------------------------
     */


  }// end of Constructor Combination()


/*
 * 目的: n,k へのアクセッサ
 * 戻り値: n,k の値
 */
  public int getN(){
    return _n;
  }
  public int getK(){
    return _k;
  }// end of getN,getK


/*
 * 目的: 指定番目(0..(nCk-1)) の組合せを返す。
 * 引数: 添字, 組合せを格納する配列
 */
  public void getElements(int count, int val[]){

  }// end of getElements


/*
 * 目的: 引数で指定された順番の順列を返す
 * 引数: 生成した順列の添字
 * 戻り値: CSV 形式の文字列
 */
  public String toString(int count){

  }// end of toString


/*
 * 目的: 組合せの数を返す
 * 戻り値: 組合せの数
 */
  public long getSize(){

  }// end of getSize


} // end of class Combination

完成したCombination クラスを利用して,次のコードを動作させましょう。このソースコードを変更する必要はありません。このままで,Combination クラスを利用してください。

ソースコード:TestCombination.java

//サンプルコード
//問題2「n 個の数値からk 個を取る組合せ」を全て列挙するプログラムを作りましょう。
//filename : TestCombination.java

import java.util.ArrayList;

class TestCombination {

  public static void main(String[] args) {

    int n=3;
    int k=2;

    Combination c = new Combination(n,k);

    System.out.println("C("+c.getN()+","+c.getK()+")="
                       +c.getSize());

    System.out.println("全ての組合せを表示します。");

    System.out.println("toString を利用");
    for(int i=0; i<c.getSize(); ++i){
      System.out.println(i + ":" + c.toString(i));
    }

    System.out.println("直接値を取得");
    int temp[] = new int[k];
    for(int i=0; i<c.getSize(); ++i){
      String result = "";
      c.getElements(i,temp);
      result += i+":";
      for(int j=0; j<temp.length; ++j){
        result += temp[j];
        if(j!=temp.length-1){
          result += ",";
        }
      }
      System.out.println(result);
    }

  }// end of main

}// end of class TestCombination

TestCombination.java の実行結果は次のようになるはずです。

C>java TestCombination
C(3,2)=3
全ての組合せを表示します。
toString を利用
0:0,1
1:0,2
2:1,2
直接値を取得
0:0,1
1:0,2
2:1,2

著者プロフィール

平田敦(ひらたあつし)

地方都市の公立工業高等学校教諭。趣味はプログラミングと日本の端っこ踏破旅行。2010年のLotYはRuby。結城浩氏のような仕事をしたいと妄想する30代後半♂。

コメント

コメントの記入