std::ranges::shuffle

Определено в заголовочном файле <algorithm>

Подпись вызова функции

Определено в заголовочном файле `<algorithm>`
Подпись вызова функции
template< std::random_access_iterator I, std::sentinel_for<I> S, class Gen > requires std::permutable<I> && std::uniform_random_bit_generator<std::remove_reference_t<Gen>> I shuffle( I first, S last, Gen&& gen );	(1)	(с C++20)
template< ranges::random_access_range R, class Gen > requires std::permutable<ranges::iterator_t<R>> && std::uniform_random_bit_generator<std::remove_reference_t<Gen>> ranges::borrowed_iterator_t<R> shuffle( R&& r, Gen&& gen );	(2)	(с C++20)

template< std::random_access_iterator I, std::sentinel_for<I> S, class Gen >
requires std::permutable<I> &&
         std::uniform_random_bit_generator<std::remove_reference_t<Gen>>
I shuffle( I first, S last, Gen&& gen );

(1)

(с C++20)

template< ranges::random_access_range R, class Gen >
requires std::permutable<ranges::iterator_t<R>> &&
         std::uniform_random_bit_generator<std::remove_reference_t<Gen>>
ranges::borrowed_iterator_t<R> shuffle( R&& r, Gen&& gen );

(2)

(с C++20)

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

2) То же, что и (1), но использует r в качестве диапазона, как если бы использовалось ranges::begin(r) в качестве first и ranges::end(r) в качестве last.

Функциональные сущности, описанные на этой странице, являются неблоидами, то есть:

Явные списки шаблонных аргументов нельзя указывать при вызове ни одной из них.
Ни одна из них не видна для поиска аргументов, зависящих от контекста.
Когда любая из них обнаружена обычным поиском без квалификаторов как имя слева от оператора вызова функции, поиск аргументов, зависящих от контекста, подавляется.

На практике они могут быть реализованы как объекты функций или с помощью специальных расширений компилятора.

Параметры

first, last	-	диапазон элементов, которые необходимо случайным образом перемешать
r	-	диапазон элементов, которые необходимо случайным образом перемешать
gen	-	генератор случайных чисел

Значение результата

Итератор, равный last.

Сложность

Точно (last - first) - 1 обменов.

Возможная реализация

struct shuffle_fn
{
    template<std::random_access_iterator I, std::sentinel_for<I> S, class Gen>
    requires std::permutable<I> &&
             std::uniform_random_bit_generator<std::remove_reference_t<Gen>>
    I operator()(I first, S last, Gen&& gen) const
    {
        using diff_t = std::iter_difference_t<I>;
        using distr_t = std::uniform_int_distribution<diff_t>;
        using param_t = typename distr_t::param_type;
        distr_t D;
        const auto n {last - first};
        for (diff_t i {1}; i < n; ++i)
            ranges::iter_swap(first + i, first + D(gen, param_t(0, i)));
        return ranges::next(first, last);
    }
 
    template<ranges::random_access_range R, class Gen>
    requires std::permutable<ranges::iterator_t<R>> &&
             std::uniform_random_bit_generator<std::remove_reference_t<Gen>>
    ranges::borrowed_iterator_t<R> operator()(R&& r, Gen&& gen) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), std::forward<Gen>(gen));
    }
};
 
inline constexpr shuffle_fn shuffle {};

Пример

#include <algorithm>
#include <array>
#include <iostream>
#include <random>
 
void print(const auto& a)
{
    for (const auto e : a)
        std::cout << e << ' ';
    std::cout << '\n';
}
 
int main()
{
    std::array a {'A', 'B', 'C', 'D', 'E', 'F'};
    print(a);
 
    std::random_device rd;
    std::mt19937 gen {rd()};
 
    for (int i {}; i != 3; ++i)
    {
        std::ranges::shuffle(a, gen);
        print(a);
    }
}

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

A B C D E F
F E A C D B
E C B F A D
B A E C F D

См. также

ranges::next_permutation (C++20)	генерирует следующую большую лексикографическую перестановку диапазона элементов (неблоид)
ranges::prev_permutation (C++20)	генерирует предыдущую меньшую лексикографическую перестановку диапазона элементов (неблоид)
random_shuffleshuffle (до C++17)(C++11)	случайным образом переупорядочивает элементы в диапазоне (шаблон функции)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/ranges/shuffle