全通りの組み合わせを羅列するプログラム

こんにちは，ABS104aです．

今回は，前回の記事の延長のような物です．

前回では全通りの探索を木構造の幅優先で探索を行いました．

今まで，あまりこういうことやってこなかったので時間がかかってしまい自分の未熟さを実感させられました．．．orz　もっと頑張らねば，

という事で，全通りの探索といって思いつく方法についてプログラムを自分で書いてみました．

一番自分で書くのがコーディング力あがるよねっ！って事でトライ．

とりあえず思いつく方法として，

・スタック

・キュー

・再帰関数

こんなところでしょうか．

まずは，スタックから行きましょう．

スタックを用いた方法では，木構造のある点における状態をスタックに格納します．

図を見てもらえれば分かるとおり，スタックでは最後に入ったオブジェクトが最初に取り出されます．最初に入ったオブジェクトは最後まで出てこない理不尽仕様です．

これによって，深さ優先探索が可能になります．要は使用したオブジェクトをすぐに使い回して条件を満たすまで掘り下げる訳です．

独自プログラム以下記述

    /**
	 * 入力したアルファベットの全通りの組み合わせを羅列するメソッド
	 * （重複あり，Stack）
	 * @param length
	 * @param value
	 */
	public static void combination_Stack(int length,char value){
		LinkedList stack = new LinkedList();
		stack.clear();
		for(int t = 0;t < value.length;t++){
			String tmpString = new String();
			tmpString += value[t];
			stack.push(tmpString);
			while(stack.size() > 0){
				tmpString = stack.pop();
				for(int s = 0;s < value.length;s++){
					String newString = new String(tmpString + value[s]);
					//判定条件（ステップ数）
					if(newString.length() == length){
						System.out.println(newString);
					}else
						stack.push(newString);
				}
			}
		}	
	}

こんな感じで実装しました．ステップ数を制限しないとドンドン掘り下がっていきます．注意．

次にキュー構造です．

キューはなじみ深いと思います．要は先入れ先出しですね．

例えば自動販売機のジュースとかはこんな感じですし，お店の行列なんかもこれです．（お店の行列がスタックだったらお客激怒ですよ(^_^;)）

これを使うことで，幅優先で探索する事が可能になります．木構造の上部から順番に下に向かって探索をします．何かの手順を探索する場合はこれを使うと多くの場合，最短手順を導き出すことができるみたいです．

独自プログラム以下記述

    /**
	 * 入力したアルファベットの全通りの組み合わせを羅列するメソッド
	 * （重複あり，Queue）
	 * @param length
	 * @param value
	 */
	public static void combination_Queue(int length,char value){
		LinkedList queue = new LinkedList();
		queue.clear();
		//RootをQueueに貯める
		for(int t = 0;t < value.length;t++){
			String tmpString = new String();
			tmpString += value[t];
			queue.offer(tmpString);
		}
		
		while(queue.size() > 0){
			for(int u = 0;u < value.length;u++){
				String tmpString = queue.poll();
				for(int t = 0;t < value.length;t++){
					String newString = new String(tmpString + value[t]);
					//判定条件（ステップ数）
					if(newString.length() == length){
						System.out.println(newString);
					}else
						queue.offer(newString);
				}
			}
		}
	}

このように組んでみました．とりあえず根が分からなかったので，厳密に言うと根の一つ下のステップからのスタートですね．

こんな雑なコードで良いのかな・・・（汗

最後に再帰関数です．

再帰関数は多分C言語とか習うと必ず一回は聞いたことあると思いますが，関数内で自分の関数を呼び出す事です．コードをミスるとすぐに無限ループ→スタックオーバーフローなので危険はありますが，物にできるとかなりスッキリした書き方ができます．

以下独自コード

   
    /**
	 * 入力したアルファベットの全通りの組み合わせを羅列するメソッド
	 * （重複あり，再帰）
	 * @param tmp
	 * @param length 組み合わせ長さ
	 * @param value 入力文字
	 */
	public static void combination_return(String tmp, int length,char[] value){
		// 検索するステップに達した時
		if(tmp.length() == length)
			System.out.println(tmp);
		// それ以外
		else {
			for (int i = 0; i < value.length; i++)
				combination_return(tmp + value[i],length, value);
		}
	}

こんな感じに書きました．かなり短く書くことができますね．便利！

これはスタックと同じで深さ優先ですかね．

場合によって使い分けれると便利そうです．

将来的に効率的なコードの実装方法を選択して組めるようになりたいなぁと思うこのこの頃です．

今日はこれぐらいで，また！