総当り(順列)を解かせる2

 

単語をばらばらにして並べ替えたものを「アナグラム」と呼びます。
例えば、グアムなら→アナグラム というようなものです。

毎度、管理人イガジーです。

このアナグラムを解く(あるいは作る)のに、総当りの並べ替えが
役に立ったりします。
という訳で、キモの再帰メソッドは、次のような感じになるでしょう。

// int []a の 0 の部分に1〜nMax の数値を入れる
// int []c は a の初期状態のコピー(0かの判別用)
void solv(int n) {
	if (n>=c.length) {
		dispa(); // 結果を出力
	}else{
		if (c[n]!=0) solv(n+1); // 初期値があったらスキップ(次へ=再帰)
		else {
			for(int i=1;i<=nMax;++i) {
				if (chkv(n,i)) { // 置けるかどうかの判定
					a[n]=i;  // 置けるならセットして
					solv(n+1); // 次の要素へ(再帰)
					a[n]=0; // 次の「置けるか判定」に備えてクリア
				}
			}
		}
	}
}


置けるかどうかの判定メソッド chkv(n,i) は、次のようになるでしょう。

boolean chkv(int n,int v){
	boolean r=true;
	for (int i=0;i<a.length;++i){
		if (a[i]==v) {r=false;break;}
	}
	return r;
}

引数 n は、使っていませんが将来の拡張用です。
(初期数値が無ければ、a.length ではなく、n までのチェックで済みます)

結果を表示するメソッド dispa() は

public void dispa(){
	System.out.println("ans:"+ans);
	for (int t:a) System.out.print(" "+t);
	System.out.println();
}

と、GUIではなく、コンソールに出力する形にしました。
for (int t:a) は、java 5以降の書き方ですが、嫌いな方は
for (int i=0;i<a.length;++i) System.out.print(" "+a[i]);としてください。
全部まとめると、次のようになります。


public class RoundRR {
	int []a,c;
	int nMax;
	int ans=0;
	RoundRR(int []x) {
		a=x;
		c=x.clone();
		nMax=a.length;
	}
	public boolean setmax(int v){
		nMax=v;
		return (v<c.length);
	}
	public void solv(){
		solv(0);
	}
	private void solv(int n) {
		if (n>=c.length) {
			++ans;
			dispa();
		}else{
			if (c[n]!=0) solv(n+1);
			else {
				for(int i=1;i<=nMax;++i) {
					if (chkv(n,i)) {
						a[n]=i;
						solv(n+1);
						a[n]=0;
					}
				}
			}
		}
	}
	public void dispa(){
		System.out.println("ans:"+ans);
		for (int t:a) System.out.print(" "+t);
		System.out.println();
	}
	boolean chkv(int n,int v){
		boolean r=true;
		for (int i=0;i<a.length;++i){
			if (a[i]==v) {r=false;break;}
		}
		return r;
	}

	public static void main(String[] args) {
		int [] x = new int [3];
		x[1]=2;
		RoundRR rrr=new RoundRR(x);
		rrr.setmax(4);
		rrr.solv();
	}

}

main(){…}には、テスト用に配列数3、最大値4、2番目の要素に2を固定
というデータをセットしています。
配列の数を変えるなどして、試してみてください。

この記事へのコメントはこちら

メールアドレスは公開されませんのでご安心ください。
また、* が付いている欄は必須項目となりますので、必ずご記入をお願いします。

内容に問題なければ、下記の「コメント送信」ボタンを押してください。