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

 

ソースコードを公開するには勇気が必要です。大丈夫だと思っていても
チョンボしてる可能性もありますし、もっとスマートに書けるかもしれません。

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

特に、なかなか思うように動かなくて四苦八苦したコードは
(美しくなかったりしますから)公開したくないものです。

でも、プログラミングに興味がある方や、必要に迫られて探してる方の
役に立てれば、と恥をしのんで公開してるのであります (^^;
ご意見、ご質問は、お手やわらかにお願いします。
こちらから→メールフォーム

という訳で、総当り並べ替え(順列)のループ版のソースコードです。
「再帰」よりは「ループ」の方が、管理人イガジーは好きなのですが
再帰版より複雑になってしまいました(工夫の余地ありそうですけれど)。

前回の記事に書いたように、元配列への書き込みはやめました。

/* 総当り並べ替え(順列)のループ版
*/
public class RoundRL {
	int []a,c;
	int nMax;
	int ans=0;

	public RoundRL(int []x){
		a=x.clone(); // 渡された配列をコピーして使用
		c=x.clone(); // 初期値記憶用
		nMax=a.length;
	}
	public void setmax(int v){
		nMax=v;
	}
	public void solv(){
		int n=0;
		while (n>=0) {
			if (n>=a.length) {
				++ans;
				if (dispa(ans,a)) break; // dispa()がtrueを返したら中断する
				n=dec(n);
				if (n<0) break;
			}else{
				if (c[n]!=0) n=inc(n); // next n(++n;)
				else {
					for(int i=a[n];;) {
						if (i<nMax) {
							++i;
							if (chkv(n,i)) {
								a[n]=i;
								n=inc(n); // next n (++n;)
								break;
							}
						}else{
							a[n]=0;
							n=dec(n); // prev n (--n;)
							break;
						}
					} // for (int i=a[n];;)
				} // else (c[n]==0)
			} //else (n<a.length)
		}// while(n>=0)
	}

	int dec(int n){
		do {
			--n;
			if (n<0) break;
			if (n>=a.length) break; // fail safe
		}while(c[n]!=0); // 初期値が入っていた箱はスキップ
		return n;
	}
	int inc(int n) {
		do {
			++n;
			if (n>=a.length) break;
		}while(c[n]!=0); // 初期値が入っていた箱はスキップ
		return n;
	}

	public boolean dispa(int an, int []aa){
		System.out.print("ans "+an+":");
		for (int t:aa) System.out.print(" "+t);
		System.out.println();
		return false; // cont
	}
	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 [] ex=new int[3];
//		ex[1]=2;
		RoundRL rl=new RoundRL(ex);
//		rl.setmax(4);
		rl.solv();
	}
}

++n; –n; の代わりとして inc(n); dec(n); を用意しました。
初期値が入っていた箱(配列)をスキップするためです。

ちょっとした改良として、dispa()から中断するか(true)、継続するか(false)を
返すようにして、if (dispa(ans,a)) break; としました。

また、class RoundRL のフィールド変数の隠蔽(カプセル化)に備えて
dispa(int an, int [] aa); と、解の番号(an)と配列(aa)を引数にしました。

このインタフェース変更にアナグラム生成プログラムを対応させるのは
そんなに難しくないと思うので、ぜひやってみてください。

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

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

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