シャッフル関数の検証

配列要素のシャッフル

上記の配列のシャッフルを偏った例1と偏っていない例2でそれぞれグラフにして表示してみました。配列を文字列に置き換えています。1の偏りがいつも同じ値になることを確かめてください。

文字列1234をシャッフルして組み合わせをカウントしています。試行回数各24000回。

環境によってサムネイル画像と違うかもしれませんが、S1では最初に4が出る組み合わせよりも、最初に2が出る組み合わせの方が1.3倍出易いという結果。

フィッシャー–イェーツのシャッフル

#include "hsp3dish.as"

#define global swap(%1,%2) tmp=%1:%1=%2:%2=tmp
#define global ascswap(%1,%2,%3) tmp=peek(%1,%2):poke %1,%2,peek(%1,%3):poke %1,%3,tmp

#module
	//==========================
	// 配列変数用
	//==========================
	// 駄目なシャッフル
	#deffunc _shuffle1 array _arr
		l = length( _arr )
		repeat l
			r = rnd( l )
			swap _arr( cnt ), _arr( r )
		loop
		return
	// Fisher–Yates shuffle
	#deffunc _shuffle2 array _arr
		l = length( _arr )
		repeat l
			r = cnt + rnd( l - cnt )
			swap _arr( cnt ), _arr( r )
		loop
		return
	//==========================
	// 文字列変数用
	//==========================
	// 駄目なシャッフル
	#defcfunc shuffle1 str _s
		s = _s
		l = strlen( s )
		repeat l
			r = rnd( l )
			ascswap s, cnt, r
		loop
		return s
	// Fisher–Yates shuffle
	#defcfunc shuffle2 str _s
		s = _s
		l = strlen( s )
		repeat l
			r = cnt + rnd( l - cnt )
			ascswap s, cnt, r
		loop
		return s
#global

	// 初期化
	randomize
	sdim s0, 8
	sdim s1, 8
	s0 = "1234"
	dim count, 5000

*test_start
	redraw 0
	
	color 32,32,32 : boxf
	// shuffle1
	repeat 24000
		s1 = shuffle1( s0 )
		count( int( s1 ) ) ++
	loop
	// 描画関係、見やすいようにしたの
	color 192, 192, 192
	line 40, 225, 600, 225
	line 40,  65, 600,  65
	y = 16
	pcnt = 0
	repeat 5000
		if count( cnt ) > 0 {
			// 1000未満赤、1000以上青
			if count( cnt ) < 1000 : color 255,128,128 : else : color 128,128,255
			// 棒グラフ
			bx = 60 + 22 * pcnt
			by = 225 - 1.0 * count( cnt ) / 25 * 4
			boxf bx, by, bx + 15, 224 
			// 値
			color 255, 255, 255
			pos 140 * ( pcnt / 6 ), y \ 97
			mes strf( "%4d:%4d", cnt, count( cnt ) )
			y += 16
			pcnt ++
			// カウンタのリセット
			count( cnt ) = 0
		}
	loop
	color 255, 255, 255
	pos   0, 0 : mes "SHUFFLE1"
	pos 540, 0 : mes "SHUFFLE1"
	
	// shuffle2
	repeat 24000
		s1 = shuffle2( s0 )
		count( int( s1 ) ) ++
	loop
	// 描画関係、見やすいようにしたの
	color 192, 192, 192
	line 40, 465, 600, 465
	line 40, 305, 600, 305
	y = 16
	pcnt = 0
	repeat 5000
		if count( cnt ) > 0 {
			// 1000未満赤、1000以上青
			if count( cnt ) < 1000 : color 255,128,128 : else : color 128,128,255
			// 棒グラフ
			bx = 60 + 22 * pcnt
			by = 465 - 1.0 * count( cnt ) / 25 * 4
			boxf bx, by, bx + 15, 464
			// 値
			color 255, 255, 255
			pos 140 * ( pcnt / 6 ), 240 + y \ 97
			mes strf( "%4d:%4d", cnt, count( cnt ) )
			y += 16
			pcnt ++
		}
	loop
	color 255, 255, 255
	pos   0, 240 : mes "SHUFFLE2"
	pos 540, 240 : mes "SHUFFLE2"
	
	redraw 1
	
	stop