STLソース解析のアルゴリズム:random_shuffle


このアルゴリズムは[first,last]の要素の順序をランダムに並べ替える.つまり、N!で可能な配列の中からランダムに1つを選び、ここでNはlast-firstである.このアルゴリズムはDonald Knuthの『コンピュータプログラム設計芸術』3.4.2節に詳しく述べている.アルゴリズムの正確性の証明は『アルゴリズム導論』5.3節を参考にすることができる.
   
   
   
   
  1. template <class RandomAccessIterator>                                             
  2. inline void random_shuffle(RandomAccessIterator first, RandomAccessIterator last) { 
  3.     if(first != last)                                                             
  4.         for(RandomAccessIterator i = first + 1; i != last; ++i)                   
  5.             iter_swap(i, first + (rand() % ((i - first) + 1)));