Defined in header <algorithm> | ||
---|---|---|
template< class RandomIt > void random_shuffle( RandomIt first, RandomIt last ); | (1) | (until C++17) (deprecated in C++14) |
(2) | ||
template< class RandomIt, class RandomFunc > void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r ); | (until C++11) | |
template< class RandomIt, class RandomFunc > void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r ); | (since C++11) (until C++17) (deprecated in C++14) | |
template< class RandomIt, class URNG > void shuffle( RandomIt first, RandomIt last, URNG&& g ); | (3) | (since C++11) |
Reorders the elements in the given range [first, last)
such that each possible permutation of those elements has equal probability of appearance.
1) The random number generator is implementation-defined, but the function
std::rand
is often used. 2) The random number generator is the function object
r
. 3) The random number generator is the function object
g
.Parameters
first, last | - | the range of elements to shuffle randomly |
r | - | function object returning a randomly chosen value of type convertible to std::iterator_traits<RandomIt>::difference_type in the interval [0,n) if invoked as r(n) |
g | - | a UniformRandomNumberGenerator whose result type is convertible to std::iterator_traits<RandomIt>::difference_type |
Type requirements | ||
- RandomIt must meet the requirements of ValueSwappable and RandomAccessIterator . | ||
- URNG must meet the requirements of UniformRandomNumberGenerator . |
Return value
(none).
Complexity
Linear in the distance between first
and last
.
Possible implementation
First version |
---|
template< class RandomIt > void random_shuffle( RandomIt first, RandomIt last ) { typename std::iterator_traits<RandomIt>::difference_type i, n; n = last - first; for (i = n-1; i > 0; --i) { using std::swap; swap(first[i], first[std::rand() % (i+1)]); } } |
Second version |
template<class RandomIt, class RandomFunc> void random_shuffle(RandomIt first, RandomIt last, RandomFunc&& r) { typename std::iterator_traits<RandomIt>::difference_type i, n; n = last - first; for (i = n-1; i > 0; --i) { using std::swap; swap(first[i], first[r(i+1)]); } } |
Third version |
template<class RandomIt, class UniformRandomNumberGenerator> void shuffle(RandomIt first, RandomIt last, UniformRandomNumberGenerator&& g) { typedef typename std::iterator_traits<RandomIt>::difference_type diff_t; typedef typename std::make_unsigned<diff_t>::type udiff_t; typedef typename std::uniform_int_distribution<udiff_t> distr_t; typedef typename distr_t::param_type param_t; distr_t D; diff_t n = last - first; for (diff_t i = n-1; i > 0; --i) { using std::swap; swap(first[i], first[D(g, param_t(0, i))]); } } |
Example
The following code randomly shuffles the integers 1..10:
#include <random> #include <algorithm> #include <iterator> #include <iostream> int main() { std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; std::random_device rd; std::mt19937 g(rd()); std::shuffle(v.begin(), v.end(), g); std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << "\n"; }
Possible output:
8 6 10 4 2 3 7 1 9 5
See also
generates the next greater lexicographic permutation of a range of elements (function template) | |
generates the next smaller lexicographic permutation of a range of elements (function template) |
Please login to continue.