今回は、
問題 「n個の数値からk個を取る順列」を全て列挙するプログラムを作りましょう
1からnまでの整数から順番にk個取り出す場合を考えましょう。そして、
出力の形式は
- カウント:1番目の数値,2番目の数値,・
・ ・ ,k番目の数値
としましょう。
順列を生成するクラスはPermutationという名前にします。以下にスケルトンを示します。正しく処理するためのコードを追加して完成させましょう。
/*
* class Permutation
* 目的: 順列に必要なメソッドを備える
*/
class Permutation {
//プライベートな変数・オブジェクトの宣言
ArrayList<ArrayList> _E = new ArrayList<ArrayList>();
int _n;
int _k;
/*
* 目的: コンストラクタ。順列に必要な変数を用意し、
* 順列を作成する。
* 引数: nPk のn,k
*/
Permutation(int n,int k){
_n = n; _k = k;
/*
-------------------------------------------
<手順>
（1）val[0]..val[_k-1]に初期値0をセットする。
Javaでは数値型配列の初期値はゼロクリアされている仕様だが、良き習慣としてゼロクリアを実行しておこう。
（2）val[_k-1]を最下位桁として、1つずつ値を増していく。val[]をn進k桁の数として扱う。
（3）こうして出来た値の列について、数値の重複する桁がないかチェックする。
（4）重複がなければ、ユニークな順列の要素として保管する。
-------------------------------------------
*/
}// end of Constructor Permutation()
/*
* 目的: n,k へのアクセッサ
* 戻り値: n,k の値
*/
public int getN(){
return _n;
}
public int getK(){
return _k;
}// end of getN,getK
/*
* 目的: 指定番目(0..(nPk-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 Permutation完成したPermutationクラスを利用して、
//サンプルコード
//問題1「n 個の数値からk 個を取る順列」を全て列挙するプログラムを作りましょう。
//filename : TestPermutation.java
import java.util.ArrayList;
class TestPermutation {
public static void main(String[] args) {
int n=3;
int k=3;
Permutation p = new Permutation(n,k);
System.out.println("P("+p.getN()+","+p.getK()+")="
+p.getSize());
System.out.println("全ての順列を表示します。");
System.out.println("toString を利用");
for(int i=0; i<p.getSize(); ++i){
System.out.println(i + ":" + p.toString(i));
}
System.out.println("直接値を取得");
int temp[] = new int[k];
for(int i=0; i<p.getSize(); ++i){
String result = "";
p.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 TestPermutationC>java TestPermutation
P(3,3)=6
全ての順列を表示します。
toString を利用
0:2,1,0
1:1,2,0
2:2,0,1
3:0,2,1
4:1,0,2
5:0,1,2
直接値を取得
0:2,1,0
1:1,2,0
2:2,0,1
3:0,2,1
4:1,0,2
5:0,1,2解説
問題 「n個の数値からk個を取る順列」
実装の方法は様々考えられます。ここに示す実装がベストであるとは思いません。むしろ色々突っ込みどころが多いと思います。特に、
ともあれ、
import java.util.ArrayList;
/*
* class Permutation
* 目的: 順列に必要なメソッドを備える
*/
class Permutation {
//プライベートな変数・オブジェクトの宣言
ArrayList<ArrayList> _E = new ArrayList<ArrayList>();
int _n;
int _k;
/*
* 目的: コンストラクタ。順列に必要な変数を用意し、
* 順列を作成する。
* 引数: nPk のn,k
*/
Permutation(int n,int k){
_n = n; _k = k;
//引数チェック
if (_k>_n || _k<0 || _n<0) {
_n=0;_k=0; //不当な引数であるため、0 とする。
}
int val[] = new int[_k];
//(1)
for(int j=0; j<_k; ++j) val[j] = 0;
//(2)
for (int j=0; j<Math.pow(_n,_k); ++j){
incrementVal(val,0);
//(3)
if (isNoDup(val) == true) {
//(4)
ArrayList<Integer> Nums = new ArrayList<Integer>();
for(int jj=0; jj<_k; ++jj) {
Nums.add(val[jj]);
}
_E.add(Nums);
}
}
}// end of Constructor Permutation()
/*
* 目的: n,k へのアクセッサ
* 戻り値: n,k の値
*/
public int getN(){
return _n;
}
public int getK(){
return _k;
}// end of getN,getK
/*
* 目的: 指定番目(0..(nPk-1)) の順列を返す。
* 引数: 添字, 順列を格納する配列
*/
public void getElements(int count, int val[]){
ArrayList<Integer> temp = new ArrayList<Integer>();
if(count < getSize()){
temp = _E.get(count);
for(int i=0; i<temp.size(); ++i){
val[i]=temp.get(i);
}
}
}// end of getElements
/*
* 目的: 引数で指定された順番の順列を返す
* 引数: 生成した順列の添字
* 戻り値: CSV 形式の文字列
*/
public String toString(int count){
ArrayList<Integer> temp = new ArrayList<Integer>();
temp = _E.get(count);
String result = "";
for (int i=0; i<_k; ++i){
result += temp.get(i);
if (i != _k-1) result += ",";
}
return result;
}// end of toString
/*
* 目的: 順列の数を返す
* 戻り値: 順列の数
*/
public long getSize(){
long size = 0;
size = factorial(_n) / factorial(_n - _k);
return size;
}// end of getSize
//- - - - - - - - - - - - - - - - - - - - - - -
//PRIVATE METHODS
//- - - - - - - - - - - - - - - - - - - - - - -
//階乗計算
private long factorial(int n) {
if ( n == 0 ) {// n が0 になったら1 を返して脱出
return 1;
} else {
return n*factorial(n-1);// 再帰呼び出し
}
}
//n 進数k 桁の数値をインクリメント
private void incrementVal(int val[],int cnt){
if(cnt >= _k){
//k 桁を超える桁上がり。全桁をゼロに。
for(int i=0; i <_k; ++i) val[i]=0;
} else {
//インクリメント操作
++val[cnt];
if(val[cnt]>=_n){
//桁上がり
for(int i=0; i <= cnt; ++i) val[i]=0;
incrementVal(val,cnt+1);
}
}
}// end of incrementVal
//引数の配列にセットされた数値の重複チェック
//重複があればfalse を返す。
private boolean isNoDup(int val[]){
int num[] = new int[_n];
for(int i=0; i<_n; ++i) num[i]=0;
for(int j=0; j<_k; ++j){
++num[val[j]];
if (num[val[j]] > 1) return false;
}
return true;
}// end of isNoDup
} // end of class Permutation今回はここまで
演習問題はいかがでしたか？
次回は今回作成したPermutationクラスを利用して、