シャッフルする

algorithm

シャッフル関連のメモ

1年前の記事

「Microsoft が提供しているブラウザ選択でランダムであるはずの表示順序に偏りがあった」という内容だ。
MS、Webブラウザ選択画面にアルゴリズム上のバグか − ＠IT
Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot
Rob Weir 氏のブログによると

  • "random shuffle" の問題は4つの approach が知られている (2 good solutions, 1 acceptable, 1 bad)

そうで、bad が使われてしまったらしい。


順列を生成して思い出したのはこのうち good のパターン

  1. 全通り並べてランダムに1つ選択する
  2. Fisher-Yates Shuffle アルゴリズム

1 番目の方法では、全通り並べるのが大変だという話だったが、i 番目の順列を生成できるようになったので問題なくなる。
2 番目は [ActionScript 3.0] Fisher-Yatesアルゴリズムの可視化│miscellaneous の Flash が素晴らしい。


次に問題の bad を見返してみる。

// DO NOT USE
function RandomSort (a,b)
{
    return (0.5 - Math.random());
}

sort は一貫した大小関係を必要とするのに comparator で引数に関係なくランダムに -0.5〜0.5 の値を返したことが原因だったらしい。
でもこの実装でも quicksort ならシャッフルできそうな気がしたので試してみる。

bad な shuffle

// DO NOT USE
def shuffle_by_qsort(List a){
  if (!a)            return []
  if (a.size() == 1) return a
  def g = a.groupBy{ (0.5 - Math.random() as BigDecimal).signum() }
  shuffle_by_qsort(g[-1]) + (g[0] ?: []) + shuffle_by_qsort(g[1])
}

def input   = "ABCDE".toList()
def results = []
10000.times {
  results << shuffle_by_qsort(input)
}

input.each { c ->
  def counts = [:].withDefault { 0 }
  results.each {
    counts[it.indexOf(c)]++
  }
  printf("$c: %3d %3d %3d %3d %3d\n", counts[0], counts[1], counts[2], counts[3], counts[4])
}

結果

A: 1984 1958 2044 1995 2019
B: 1999 2060 2049 1948 1944
C: 2025 1971 1991 2049 1964
D: 2033 2050 1980 1956 1981
E: 1959 1961 1936 2052 2092

quicksort は qsort - ellaneous を参考にした。
comparator 以外にも変更を加えているのは random() がまず 0.5 を返さないので、要素が 1つのリストは無限ループしてしまうからだ。実行してみるとシャッフルできる。*1
ではどの sort なら偏った結果になるのか？ ブログのグラフでは 4, 5 に大きな偏りがみられる。merge sort なら 4, 5 に偏りがあれば 1, 2 にも偏りがあるはずなので、O(n^2) の sort だと予想しているのだがそれはまた気が向いたら調べることにする。

5年前のブログ

残った acceptable は最初にすべての要素に乱数を振る方法だ。
次の一連のブログが参考になった。*2
JavaScriptの配列をsort関数でシャッフルする - snippets from shinichitomita’s journal
404 Blog Not Found:javascript - シャッフルシャッフル
きまぐれ日記: Schwartzian Transform でランダムシャッフル
404 Blog Not Found:int rand() と Math.random() の違い

2点が good にならない理由

  • shuffle は O(n) でできるのに O(n log(n)) の sort で行う必要はない
  • 実用上問題ないが厳密には偏りがある (k ** n % n! != 0)*3

6年前のクイズ

O(n) だが偏りが無視できない？ケース
[結] 2005年10月 - 結城浩の日記
[結] 2005年10月 - 結城浩の日記
少ない数で試してみるという態度が極めて重要らしいので試してみる。

def cs     = ('A'..'C').toList()
def n      = cs.size()
def rs     = [(0..<n), (0..<n), (0..<n)].combinations()
def counts = new int[3][3]  // counts[index of c][index of shuffled]
 
rs.each {
  def shuffled = cs.clone()
  it.eachWithIndex { r, i ->
    Collections.swap(shuffled, r, i)
  }
  shuffled.eachWithIndex { c, i ->
    counts[cs.indexOf(c)][i]++
  }
}
 
counts.eachWithIndex { count, i ->
  println "${cs[i]} = $count"
}
// A = [9, 9, 9]
// B = [10, 8, 9]
// C = [8, 10, 9]

乱数の取り得るパターンをすべて試して A, B, C が等しくなれば偏りがないわけだが 3^3 は 3! で割り切れないので等しくならない。

*1:試してから気づいたがコメント欄にも quicksort ならシャッフルできることは書かれていてた

*2:Schwartzian Transform も学習した

*3:でも k が大きいので問題にならない