std::random_shuffle, std::shuffle

Материал из cppreference.com

This page has been machine-translated from the English version of the wiki using Google Translate.

The translation may contain errors and awkward wording. Hover over text to see the original version. You can help to fix errors and improve the translation. For instructions click here.

Заголовочный файл `<algorithm>`

template< class RandomIt > void random_shuffle( RandomIt first, RandomIt last );	(1)

template< class RandomIt, class RandomFunc > void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r ); template< class RandomIt, class RandomFunc > void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r );	(2)	(до C++11) (начиная с C++11)

template< class RandomIt, class URNG > void shuffle( RandomIt first, RandomIt last, URNG&& g );	(3)	(начиная с C++11)

Изменяет порядок элементов в заданном диапазоне [first, last) такой, что каждой возможной перестановкой этих элементов имеет одинаковую вероятность появления.

1)

Генератор случайных чисел определяется реализацией, но функция std::rand часто используется.

2)

Генератор случайных чисел является r объект функции.

3)

Генератор случайных чисел является g объект функции.

[править] Параметры

first, last	-	диапазон элементов в случайном порядке Original: the range of elements to shuffle randomly The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
r	-	Функция объект возвращается случайно выбранное значение типа, конвертируемых в `iterator_traits<RandomIt>::difference_type` в интервале [0, п), если вызывается как `r(n)` Original: function object returning a randomly chosen value of type convertible to `iterator_traits<RandomIt>::difference_type` in the interval [0,n) if invoked as `r(n)` The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
g	-	Функция объект возвращается случайно выбранное значение типа `URNG::result_type` в интервале [g.min (), g.max ()], если вызывается как `g()` (например, любой из равномерного генератора случайных чисел из `<random>`) Original: function object returning a randomly chosen value of type `URNG::result_type` in the interval [g.min(), g.max()] if invoked as `g()` (e.g. any of the uniform random number generators from `<random>`) The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
Type requirements
- `RandomIt` must meet the requirements of `ValueSwappable` and `RandomAccessIterator`.
- `URNG` must meet the requirements of `UniformRandomNumberGenerator`.

[править] Возвращаемое значение

(Нет)

[править] Сложность

линейные по расстоянию между first и last

[править] Возможная реализация

First 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)]);
    }
}

Second 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))]);
    }
}

[править] Пример

Следующий код смешает случайным образом числа 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);
 
    copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}

Возможный выход:

8 6 10 4 2 3 7 1 9 5

[править] См. также


next_permutation	generates the next greater lexicographic permutation of a range of elements (шаблон функции) [edit]

prev_permutation	generates the next smaller lexicographic permutation of a range of elements (шаблон функции) [edit]

Язык
Понятия
Утилиты библиотеки
Струны библиотеки
Контейнеры библиотеки
Алгоритмы библиотеки
Итераторы библиотеки
Numerics библиотеки
Библиотеки ввода / вывода
Локализация библиотеки
Библиотеки регулярных выражений (C++11)
Атомная библиотеке операций (C++11)
Библиотека тему поддержки (C++11)

cppreference.com

Поиск

Пространства имён

Варианты

Просмотры

Действия