アルゴリズム基礎2:ボールを順番に取り出す問題を通してシャッフルアルゴリズムを学ぶ

ボールを順番に取り出す問題を通してシャッフルについて考察してみよう。

お題

今回扱うお題は以下

袋の中に5つのボールが入っている。このボールには1から5の番号がついている。ちょうどビリヤードのボールが袋に5個入っていることを想像してもらえればよい。この袋から一つずつボールを取り出したととする。その時のボール番号を順番に表示する処理を作成せよ。(取り出したボールは袋に戻さない)

[実行例](実行するたびに変わる)

[3,5,2,4,1]

ポイント

ランダムに取り出すことになりそうだが、同じボールを取り出すことはできない
この部分をどう考えるかがポイントになりそうだ。

色々やり方はありそう。。。

まずはいろいろなやり方を考えてみよう。

番号を抽選して、過去に出ていたらやり直す

出た目を配列に入れていって、もし過去に出ていた番号だったら抽選し直すという方法だ。

import java.util.*;

public class Test {
	public static void main(String[] args){
		int[] balls=new int[5];//すべて0
		boolean isExists;//過去に出たフラグ
		int now;//抽選した番号
		//5回繰り返す
		for(int i=0;i<balls.length;i++){
			do{
				isExists=false;
				now=new Random().nextInt(5)+1;//1から5を抽選
				//過去に出ていたら
				for(int ball:balls){
					if(now == ball){
						isExists = true;//過去に出たフラグをtrue
					}
				}
			}while(isExists);//過去に出ていたら抽選し直し
			balls[i]=now;//ここに来たということは新しい番号なので配列にいれる。
		}
		System.out.println(Arrays.toString(balls));
	}
}

なるほど、これならば確かに実現できる。ただ、ボールが1000個になった場合、最後の方になると新しい目を抽選するのがとても大変そうだ。

複数回交換してみる

最初に1から5の配列を用意してランダムに2値を入れ替えるという方法も考えられる。

import java.util.Random;

public class Test {
	public static void main(String[] args){
		int[] balls = {1,2,3,4,5};
		for(int i = 0;i< balls.length*2;i++){
			int id1=new Random().nextInt(balls.length);
			int id2=new Random().nextInt(balls.length);
			if(id1 != id2){
				int tmp=balls[id1];
				balls[id1]=balls[id2];
				balls[id2]=tmp;
			}
		}
		System.out.println(Arrays.toString(balls));
	}
}

これならばボールの数が増えても問題がなさそうだ。ただ、今回は適当にボールの数の2倍回数分ボールの入れ替え(swap)を行ってみたがこれは適当な回数なのだろうか?

解答例

では正解となる考え方を順番に見ていこう。
まず、最初の1つ目だがこれは5個のボールからランダムに選べば良い。
仮に3が選ばれたとしよう

一番先頭の値(1)と交換する

このような状態になった

3番はもう引くことができない。次は残りの4つから一つをランダム抽選する。

5番が選ばれた

今度は先頭から2つ目のボールと交換する

このような状態になる

3番と5番のボールは引けないので残りの3つから抽選する

2番が選ばれた。

先頭から3番目のボールと交換する

このような状態になった。

最後に残り2つから抽選する

4番が選ばれた

交換の必要はない

最後の一つは抽選する必要がない。

今回の結果は

3,5,2,4,1

だったようだ。

上でやったことをコードで書いてみる

import java.util.*;
public class Test {
	public static void main(String[] args) {
		int[] balls ={1,2,3,4,5};
		//ボールの抽選回数はボールの数-1(最後の1個は抽選しなくてよい)
		for(int i=0;i<balls.length-1;i++){
			//選ばれるボールのindex,一つ選ぶたびに抽選範囲が一つずつ狭まる
			//最初0-4(全部)
			//次1-4(最初をのぞく残り)
			//次2-4
			//次3か4
			int index = new java.util.Random().nextInt(balls.length-i)+i;
			int tmp = balls[index];//選ばれたボールの番号
			balls[index] = balls[i];//最初の要素とswap
			balls[i] = tmp;
		}
		System.out.println(Arrays.toString(balls));
	}
}

コメント部分を除去したコードが以下

import java.util.*;
public class Test {
	public static void main(String[] args) {
		int[] balls ={1,2,3,4,5};
		for(int i=0;i<balls.length-1;i++){
			int index = new java.util.Random().nextInt(balls.length-i)+i;
			int tmp = balls[index];
			balls[index] = balls[i];
			balls[i] = tmp;
		}
		System.out.println(Arrays.toString(balls));
	}
}

これがボールを袋からランダムに取り出すという行為を確率も含め忠実に再現したコードとなる、これは結果として配列をシャッフルするアルゴリズムとなっている。

大事なこと

今回はボールを袋から取り出すお題をテーマに配列をシャッフルするアルゴリズムについて学習した。大事なことは上のソースコードを覚えることではなく、上で詳細に行った考え方をしっかりと理解することだ。こういった考え方を一つ一つ理解していくことでプログラミングのセンスが磨かれていく

Java
スポンサーリンク
シェアする
mjpurinをフォローする
ジョイタスネット

コメント

タイトルとURLをコピーしました