シャッフルアルゴリズム

はじめに

配列が与えられたとき、それをバラバラに並び替えたい。
C++のSTLのrandom_shuffle関数を実現したい。

Fisher-Yates shuffle

http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

一番使われていると思われるシャッフルアルゴリズム。
n個の配列のうち、n番目の数字と、1番目からn番目のどれかをswap。n番目はもう決定したので、これを除いたn-1個の配列
について同様のことを繰り返す。O(N)。

//http://www.cplusplus.com/reference/algorithm/random_shuffle/
template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last,
                      RandomNumberGenerator& rand )
{
  iterator_traits<RandomAccessIterator>::difference_type i, n;
  n = (last-first);
  for (i=n-1; i>0; --i) swap (first[i],first[rand(i+1)]);
}

他の方法

配列の要素に「優先度」をランダムにつけ、その優先度順に並び替える

一番ナイーブな方法かもしれない。
偏りがない証明がどうなっているかは「アルゴリズムイントロダクション第1巻」のpp.96-97あたり。O(NlogN)。

struct P {
  int v, p;
};
bool operator<(P a, P b){
  return a.p < b.p;
}

void random_shuffle(std::vector<int> &v){
  std::vector<P> pv;
  for(size_t i=0; i<v.size(); i++){
    pv.push_back((P){v[i],rand()%10000000});
  }
  std::sort(pv.begin(), pv.end());
  for(size_t i=0; i<v.size(); i++){
    v[i] = pv[i].v;
  }
}

javascriptでこれに近い方法を取ろうとして失敗した事件があったみたい。
http://www.atmarkit.co.jp/news/201003/01/ballot.html
ブラウザの選択画面にでるブラウザの順番をシャッフルしたいが、2つの優先度の比較に

hoge.sort(RandomSort);

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

としたために、推移性が保障されずうまくいかなかったらしい。気を付けたい。