Shuffle a vector in C++
This post will discuss how to shuffle a vector in C++.
1. Using std::random_shuffle function
The idea is to use the std::random_shuffle algorithm defined in the <algorithm> header. The C++ specification does not state the source of randomness for its built-in random generator and can be used with C++98/03 standard.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> #include <vector> #include <algorithm> void print(std::vector<int> const &v) { for (int i: v) { std::cout << i << ' '; } } int main() { std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; std::random_shuffle(v.begin(), v.end()); print(v); return 0; } |
We can also add a custom random number generator as an additional argument to the std::random_shuffle function, as shown below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> #include <vector> #include <algorithm> void print(std::vector<int> const &v) { for (int i: v) { std::cout << i << ' '; } } int main() { std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; std::random_shuffle(v.begin(), v.end(), [&](int i) { return std::rand() % i; }); print(v); return 0; } |
2. Using std::shuffle function
From C++11 onward, we should prefer std::shuffle over std::random_shuffle. It randomly rearranges the elements in the specified range using the specified uniform random number generator. We can use any of the standard generators defined in the <random> header introduced with C++11.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> #include <vector> #include <algorithm> #include <random> void print(std::vector<int> const &v) { for (int i: v) { std::cout << i << ' '; } } int main() { std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; std::shuffle(std::begin(v), std::end(v), std::default_random_engine()); print(v); return 0; } |
The std::default_random_engine generator produces the same output every time. To get a different output, the idea is to use a custom random number generator that can be seeded from an external source.
|
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 |
#include <iostream> #include <vector> #include <algorithm> #include <random> #include <chrono> void print(std::vector<int> const &v) { for (int i: v) { std::cout << i << ' '; } } int main() { std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // get a time-based seed unsigned seed = std::chrono::system_clock::now() .time_since_epoch() .count(); shuffle (v.begin(), v.end(), std::default_random_engine(seed)); print(v); return 0; } |
3. Using Fisher-Yates Shuffle Algorithm
Another good alternative is to use Fisher–Yates shuffle to generate random permutations. The algorithm does a linear scan of the vector and swaps each element with a random element among all remaining elements, including the element itself.
|
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 |
#include <iostream> #include <vector> #include <algorithm> void print(std::vector<int> const &v) { for (int i: v) { std::cout << i << ' '; } } int main() { std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = v.size(); for (int i = 0; i < n - 1; i++) { // generate a random number `j` such that `i <= j < n` and // swap the element present at index `j` with the element // present at current index `i` int j = i + rand() % (n - i); std::swap(v[i], v[j]); } print(v); return 0; } |
That’s all about shuffling a vector in C++.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)