🔄

シャッフルアルゴリズムと精度検証

2023/07/29に公開

Ruby

アルゴリズム

shuffle

tech

まずシャッフル度を測定できるようにする

def test
  try = 1000_0000
  r = try.times.collect {
    a = 10.times.to_a
    yield a
    a.each_cons(2).count { _1 < _2 }.fdiv(a.size - 1)
  }.sum.fdiv(try)
  (r - 0.5).round(4)
end

これを使うと上手に混ぜるほど 0 に近い値が返る。

例:

デフォルトのまますべてが昇順に並んでいるとき

test { |a| a }  # => 0.5

すべて降順のとき

test { |a| a.reverse! }  # => -0.5

Ruby の組み込みメソッドの場合

test { |a| a.shuffle! }  # => 0.0

ここからいろいろ試してみる。

半周分ランダムに二箇所を入れ替える

一回の入れ替えで二箇所の配置が変わるんだから全体の個数の半分入れ替えればちょうど全体が混ざるんじゃないかと考えたもの。

r = test do |a|
  (a.size / 2).times do |i|
    i = rand(a.size)
    j = rand(a.size)
    a[i], a[j] = a[j], a[i]
  end
end
r  # => 0.0639

結果: 昇順の痕跡が強く残っている

一周分ランダムに二箇所を入れ替える

一度もアクセスされていない要素があるんじゃないかと思われるので倍の一周分にしてみる。

r = test do |a|
  a.each_index do |i|
    i = rand(a.size)
    j = rand(a.size)
    a[i], a[j] = a[j], a[i]
  end
end
r  # => 0.0132

結果: よくなったけどそれでも偏っている

二周分ランダムに二箇所を入れ替える

交換回数をさらに倍にする。

r = test do |a|
  (a.size * 2).times do |i|
    i = rand(a.size)
    j = rand(a.size)
    a[i], a[j] = a[j], a[i]
  end
end
r  # => 0.0012

結果: かなりよくなってきたけどまだ偏っている

もっと精度を上げるにはさらに何周もすればいいのかもしれないけど冷静に考えれば一周で充分である。これは両方ランダムなのがダメなのだろう。

片方だけランダムで一周する

一方は配列を走査するので必ず入れ替えが起きるはず。

r = test do |a|
  a.each_index do |i|
    j = rand(a.size)
    a[i], a[j] = a[j], a[i]
  end
end
r  # => 0.0058

結果: ！？

これで完成だと思っていたのにまだ昇順に偏っているのはどうしてだろう？考えられるとすれば同じ二箇所を偶数回入れ替えて元に戻ってしまっているとしか思えない。

フィッシャーとイェーツによるアルゴリズム

このアルゴリズムでは同じ二箇所を二回以上入れ替えないようになっている。
https://ja.wikipedia.org/wiki/フィッシャー–イェーツのシャッフル

r = test do |a|
  (a.size - 1).downto(1) do |i|
    j = rand(i + 1)
    a[j], a[i] = a[i], a[j]
  end
end
r  # => 0.0

さすがの精度である。

ランダム値を求める範囲が徐々に狭まっていくのが特徴で Ruby の組み込みメソッド shuffle! も同じようになっているのがわかる。 (RAND_UPTO(i) の i が徐々に減っている)

フィッシャーとイェーツによるアルゴリズムの out-of-place 版

フィッシャーとイェーツによるアルゴリズムの本来の仕組みは「ランダムに取り出して並べる」ただそれだけなのでコードもその通りに書いてみる。

r = test do |a|
  b = a.dup
  c = []
  until b.empty?
    c << b.delete_at(rand(b.size))
  end
  a.replace(c)
end
r  # => -0.0

これが out-of-place 版になる。

なので組み込みの機能が用意されてなくて、メモリを気にしないでよくて、アルゴリズムを絶対に間違えたくないならこの out-of-place 版のロジックで書けばいい。