powered by hsp3dish.js / OpenHSP
上記の配列のシャッフルを偏った例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