FisherYates

構文
FisherYates( var arr[] )
引数
var arr[]
シャッフルする配列(参照引数)
戻値

プログラム

//////////////////////////////////////////////////
// 【引数】
//   var arr[] : シャッフルする配列(参照引数) 
// 【戻値】
//   
//////////////////////////////////////////////////
PROCEDURE FisherYates(var arr[])
	FOR n = UBound(arr) TO 0 STEP -1
		DIM num = RANDOM(n+1)
		DIM tmp = arr[n]
		arr[n] = arr[num]
		arr[num] = tmp
	NEXT
FEND

//////////////////////////////////////////////////
// 【引数】
//   配列 : 上限値を求める配列 
// 【戻値】
//   配列の上限値 
//////////////////////////////////////////////////
FUNCTION UBound(array[])
	RESULT = RESIZE(array)
FEND

プログラム実行例

配列の中身をシャッフルして出力

DIM arr[] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

FisherYates(arr)

FOR item IN arr
	PRINT item
NEXT

//////////////////////////////////////////////////
// 【引数】
//   var arr[] : シャッフルする配列(参照引数) 
// 【戻値】
//   
//////////////////////////////////////////////////
PROCEDURE FisherYates(var arr[])
	FOR n = UBound(arr) TO 0 STEP -1
		DIM num = RANDOM(n+1)
		DIM tmp = arr[n]
		arr[n] = arr[num]
		arr[num] = tmp
	NEXT
FEND

//////////////////////////////////////////////////
// 【引数】
//   配列 : 上限値を求める配列 
// 【戻値】
//   配列の上限値 
//////////////////////////////////////////////////
FUNCTION UBound(array[])
	RESULT = RESIZE(array)
FEND
    (3)
結果
4
7
3
9
1
10
2
5
8
6

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

フィッシャー-イェーツのシャッフルとは、有限集合からランダムな順列を生成するアルゴリズムです。処理の流れは、くじ引きボックスに入れた紙を1枚ずつ取り出して並べるイメージです。

処理時間はシャッフルされる要素数に比例します。