Difference between revisions of "cpp/algorithm/ranges/shuffle"
From cppreference.com
(Undo revision 137567 by Space Mission (talk). Can't both start at 1 and use != otherwise empty ranges cause UB) |
m (→Synopsis: (1) - less misleading.) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 2: | Line 2: | ||
{{cpp/algorithm/ranges/navbar}} | {{cpp/algorithm/ranges/navbar}} | ||
{{dcl begin}} | {{dcl begin}} | ||
| − | {{dcl header | algorithm}} | + | {{dcl header|algorithm}} |
| − | {{dcl h | Call signature}} | + | {{dcl h|Call signature}} |
| − | {{dcl | num=1 | since=c++20 |1= | + | {{dcl|num=1|since=c++20|1= |
template< std::random_access_iterator I, std::sentinel_for<I> S, class Gen > | template< std::random_access_iterator I, std::sentinel_for<I> S, class Gen > | ||
| − | requires | + | requires std::permutable<I> && |
| − | + | std::uniform_random_bit_generator<std::remove_reference_t<Gen>> | |
| − | I shuffle( I first, S last, Gen&& gen ); | + | I shuffle( I first, S last, Gen&& gen ); |
}} | }} | ||
| − | {{dcl | num=2 | since=c++20 |1= | + | {{dcl|num=2|since=c++20|1= |
template< ranges::random_access_range R, class Gen > | template< ranges::random_access_range R, class Gen > | ||
| − | requires | + | 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 ); | + | ranges::borrowed_iterator_t<R> |
| + | shuffle( R&& r, Gen&& gen ); | ||
}} | }} | ||
{{dcl end}} | {{dcl end}} | ||
| − | @1@ Reorders the elements in the given range {{ | + | @1@ Reorders the elements in the given range {{range|first|last}} such that each possible permutation of those elements has equal probability of appearance. |
| − | @2@ Same as {{v|1}}, but uses {{ | + | @2@ Same as {{v|1}}, but uses {{c|r}} as the range, as if using {{c|ranges::begin(r)}} as {{c|first}} and {{c|ranges::end(r)}} as {{c|last}}. |
{{cpp/ranges/niebloid}} | {{cpp/ranges/niebloid}} | ||
| Line 26: | Line 27: | ||
===Parameters=== | ===Parameters=== | ||
{{par begin}} | {{par begin}} | ||
| − | {{par | first, last | the range of elements to shuffle randomly}} | + | {{par|first, last|the range of elements to shuffle randomly}} |
| − | {{par | r | the range of elements to shuffle randomly}} | + | {{par|r|the range of elements to shuffle randomly}} |
| − | {{par | gen | the random number generator}} | + | {{par|gen|the random number generator}} |
{{par end}} | {{par end}} | ||
===Return value=== | ===Return value=== | ||
| − | An iterator equal to {{ | + | An iterator equal to {{c|last}}. |
===Complexity=== | ===Complexity=== | ||
| − | Exactly {{ | + | Exactly {{c|(last - first) - 1}} swaps. |
===Possible implementation=== | ===Possible implementation=== | ||
| − | {{eq fun | 1= | + | {{eq fun|1= |
| − | struct shuffle_fn { | + | struct shuffle_fn |
| − | + | { | |
| + | template<std::random_access_iterator I, std::sentinel_for<I> S, class Gen> | ||
requires std::permutable<I> && | requires std::permutable<I> && | ||
std::uniform_random_bit_generator<std::remove_reference_t<Gen>> | 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>> && | requires std::permutable<ranges::iterator_t<R>> && | ||
std::uniform_random_bit_generator<std::remove_reference_t<Gen>> | 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{}; | + | inline constexpr shuffle_fn shuffle {}; |
}} | }} | ||
===Example=== | ===Example=== | ||
| − | {{example | code= | + | {{example|code= |
#include <algorithm> | #include <algorithm> | ||
#include <array> | #include <array> | ||
| Line 73: | Line 76: | ||
#include <random> | #include <random> | ||
| − | void print(const auto& a) { | + | void print(const auto& a) |
| − | for (const auto e : a) | + | { |
| − | std::cout << | + | for (const auto e : a) |
| + | std::cout << e << ' '; | ||
| + | std::cout << '\n'; | ||
} | } | ||
int main() | int main() | ||
{ | { | ||
| − | std::array a{'A', 'B', 'C', 'D', 'E', 'F'}; | + | std::array a {'A', 'B', 'C', 'D', 'E', 'F'}; |
print(a); | print(a); | ||
std::random_device rd; | std::random_device rd; | ||
| − | std::mt19937 gen{rd()}; | + | std::mt19937 gen {rd()}; |
| − | for (int i{}; i != 3; ++i) { | + | for (int i {}; i != 3; ++i) |
| + | { | ||
std::ranges::shuffle(a, gen); | std::ranges::shuffle(a, gen); | ||
print(a); | print(a); | ||
} | } | ||
} | } | ||
| − | | p=true | + | |p=true |
| − | | output= | + | |output= |
A B C D E F | A B C D E F | ||
F E A C D B | F E A C D B | ||
| Line 101: | Line 107: | ||
===See also=== | ===See also=== | ||
{{dsc begin}} | {{dsc begin}} | ||
| − | {{dsc inc | cpp/algorithm/ranges/dsc next_permutation}} | + | {{dsc inc|cpp/algorithm/ranges/dsc next_permutation}} |
| − | {{dsc inc | cpp/algorithm/ranges/dsc prev_permutation}} | + | {{dsc inc|cpp/algorithm/ranges/dsc prev_permutation}} |
| − | {{dsc inc | cpp/algorithm/dsc random_shuffle}} | + | {{dsc inc|cpp/algorithm/dsc random_shuffle}} |
{{dsc end}} | {{dsc end}} | ||
{{langlinks|de|es|fr|it|ja|pt|ru|zh}} | {{langlinks|de|es|fr|it|ja|pt|ru|zh}} | ||
Latest revision as of 12:06, 23 April 2024
| Defined in header <algorithm>
|
||
| Call signature |
||
| template< std::random_access_iterator I, std::sentinel_for<I> S, class Gen > requires std::permutable<I> && |
(1) | (since C++20) |
| template< ranges::random_access_range R, class Gen > requires std::permutable<ranges::iterator_t<R>> && |
(2) | (since C++20) |
1) Reorders the elements in the given range
[first, last) such that each possible permutation of those elements has equal probability of appearance.2) Same as (1), but uses r as the range, as if using ranges::begin(r) as first and ranges::end(r) as last.
The function-like entities described on this page are niebloids, that is:
- Explicit template argument lists cannot be specified when calling any of them.
- None of them are visible to argument-dependent lookup.
- When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.
In practice, they may be implemented as function objects, or with special compiler extensions.
Contents |
[edit] Parameters
| first, last | - | the range of elements to shuffle randomly |
| r | - | the range of elements to shuffle randomly |
| gen | - | the random number generator |
[edit] Return value
An iterator equal to last.
[edit] Complexity
Exactly (last - first) - 1 swaps.
[edit] Possible implementation
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 {}; |
[edit] Example
Run this code
#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); } }
Possible output:
A B C D E F F E A C D B E C B F A D B A E C F D
[edit] See also
| (C++20) |
generates the next greater lexicographic permutation of a range of elements (niebloid) |
| (C++20) |
generates the next smaller lexicographic permutation of a range of elements (niebloid) |
| (until C++17)(C++11) |
randomly re-orders elements in a range (function template) |
