random_shuffle


function template
<algorithm>
template <class RandomAccessIterator>
  void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class RandomNumberGenerator>
  void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last,
                        RandomNumberGenerator& rand );

Rearrange elements in range randomly

Rearranges the elements in the range [first,last) randomly.

The function swaps the value of each element with that of some other randomly chosen element. When provided, the function rand chooses which element.

The behavior of this function template is equivalent to:
1
2
3
4
5
6
7
8
 
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=2; i<n; ++i) swap (first[i],first[rand(i)]);
}


Parameters

first, last
Forward iterators to the initial and final positions of the sequence to be shuffled. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
rand
Pointer to unary function taking one argument and returning a value, both of the appropriate difference type (generally ptrdiff_t). The function shall return a value between zero and its argument (lower than this).


Return value

none

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
// random_shuffle example
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;

// random generator function:
ptrdiff_t myrandom (ptrdiff_t i) { return rand()%i;}

// pointer object to it:
ptrdiff_t (*p_myrandom)(ptrdiff_t) = myrandom;

int main () {
  srand ( unsigned ( time (NULL) ) );
  vector<int> myvector;
  vector<int>::iterator it;

  // set some values:
  for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9

  // using built-in random generator:
  random_shuffle ( myvector.begin(), myvector.end() );

  // using myrandom:
  random_shuffle ( myvector.begin(), myvector.end(), p_myrandom);

  // print out content:
  cout << "myvector contains:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}


A possible output:
myvector contains: 3 4 1 6 8 9 2 7 5


Complexity

Linear: As many calls to swap as the length of the range [first,last) minus 1.

See also

rotate Rotate elements in range (function template)
reverse Reverse range (function template)
generate Generate values for range with function (function template)
swap Exchange values of two objects (function template)