Fisher-Yates法の改良

0～N-1の数列をシャッフルした数列を連続して生成する必要があったので軽く調査。

よく見かけるのは0～N-1の数列を生成してからFisher-Yates法で内部シャッフルするアルゴリズムだが、繰り返し生成するとなると1周する都度の初期化コスト(O(n))が馬鹿にならない。

O(n)のワークメモリが必要だが、1周ごとの初期化コストがO(1)になるように改良してみた。

ポイントは数値の取り出し方とメモの取り方。

UniqRand.rb

# !ruby

##
## 重複なし乱数の生成(Fisher-Yates改)
##
#
# 長さNで(0 .. N-1)の重複しない乱数の繰り返し
#
# UniqRand.new(size) : 長さsizeで乱数を初期化
# UniqRand.getNext : 乱数を取り出す
#
class UniqRand
	private
	# メモから数値を取り出す
	def readMemo(i)
		# 指定されたインデックスの更新状況を確認
		if @flags[i] != @mark # 未更新なら
			# インデックス値でメモを更新
			@values[i] = i
			# 更新済みフラグをマーク
			@flags[i] = @mark
		end
		# 更新済みであればメモから返す
		@values[i]
	end

	public
	def initialize(size)
		@size = size	# 数列の長さ
		@index = 0		# 乱数の取り出し位置
		@mark = false	# 更新済みマーカー
		@flags = Array.new(@size, !@mark)	# 更新済みフラグ
		@values = Array.new(@size)			# 数列メモ
	end

	# 数値を取り出す
	def getNext
		# 1周終わったら数列を初期化
		if @index >= @size
			# マーカーを更新
			@mark = !@mark
			# 取り出し位置を巻き戻す
			@index = 0
		end
		# シャッフル先をランダムに決める
		ptr = rand(@index .. @size - 1)

		# 取り出し位置とシャッフル先について、メモから数値を取り出す
		# ※メモを更新するので先に両方共取り出しておくこと
		dst = readMemo(ptr)
		src = readMemo(@index)

		# 取り出した値を入れ替える
		@values[ptr] = src
		@values[@index] = dst

		# 取り出し位置を更新
		@index += 1

		# 取り出した値を返す
		return dst
	end
end

以下テスト

# 0..9の乱数発生器を生成
N = 10
urnd = UniqRand.new(N)

5.times {
	# 10個の乱数を取得
	lst = Array.new(N){urnd.getNext}
	p lst
	# 重複・範囲外がないことをチェック
	raise unless lst.uniq.size == N && lst.all?{|n| n.between?(0,N-1)}
}