前回は順列を生成するクラスを作成しました。nPkの公式を知っていれば,
問題2 「n個の数値からk個を取る組合せ」を全て列挙するプログラムを作りましょう。
1からnまでの整数からk個取り出す場合を考えましょう。そして,
出力の形式は
- カウント:1番目の数値,2番目の数値,・
・ ・ ,k番目の数値
としましょう。
組合せを生成するクラスはCombinationという名前にします。以下にスケルトンを示します。正しく処理するためのコードを追加して完成させましょう。
ソースコード:Combination.
/*
* 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 クラスを利用して,
ソースコード:TestCombination.
//サンプルコード
//問題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.
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