
Category: algorithms  Component type: function 
template <class RandomAccessIterator> void random_shuffle(RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class RandomNumberGenerator> void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand)
const int N = 8; int A[] = {1, 2, 3, 4, 5, 6, 7, 8}; random_shuffle(A, A + N); copy(A, A + N, ostream_iterator<int>(cout, " ")); // The printed result might be 7 1 6 3 2 5 4 8, // or any of 40,319 other possibilities.
[1] This algorithm is described in section 3.4.2 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, second edition. AddisonWesley, 1981). Knuth credits Moses and Oakford (1963) and Durstenfeld (1964). Note that there are N! ways of arranging a sequence of N elements. Random_shuffle yields uniformly distributed results; that is, the probability of any particular ordering is 1/N!. The reason this comment is important is that there are a number of algorithms that seem at first sight to implement random shuffling of a sequence, but that do not in fact produce a uniform distribution over the N! possible orderings. That is, it's easy to get random shuffle wrong.
Contact Us  Site Map  Trademarks  Privacy  Using this site means you accept its Terms of Use 
Copyright © 2009  2017 Silicon Graphics International. All rights reserved. 