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