How to Shuffle a Std::Vector

How to shuffle a std::vector?

From C++11 onwards, you should prefer:

#include <algorithm>
#include <random>

auto rng = std::default_random_engine {};
std::shuffle(std::begin(cards_), std::end(cards_), rng);

Live example on Coliru

Make sure to reuse the same instance of rng throughout multiple calls to std::shuffle if you intend to generate different permutations every time!

Moreover, if you want your program to create different sequences of shuffles each time it is run, you can seed the constructor of the random engine with the output of std::random_device:

auto rd = std::random_device {}; 
auto rng = std::default_random_engine { rd() };
std::shuffle(std::begin(cards_), std::end(cards_), rng);

---

For C++98 you may use:

#include <algorithm>

std::random_shuffle(cards_.begin(), cards_.end());

Is there a better way of shuffling a vector in C++?

std::shuffle in <algorithm> should be what you're looking for. Here's an example of it in use.

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>

int main () {
  std::vector<int> myvector {1,2,3,4,5};

  std::random_device rd;
  std::default_random_engine gen(rd);

  std::shuffle (myvector.begin(), myvector.end(), gen);

  for (int& x: myvector) std::cout << ' ' << x;
  std::cout << std::endl;

  return 0;
}

This example is adapted to use vectors from a version found at http://www.cplusplus.com/reference/algorithm/shuffle/. Checkout the link for more info on std::shuffle

Fastest trivial way of shuffling a vector

There is a tradeoff to be made: Shuffling a a std::vector<size_t> of indices can be expected to be cheaper than shuffling a std::vector<Position> at the cost of an indirection when accessing the Positions via shuffled indices. Actually the example on cppreference for std::iota is doing something along that line (it uses iterators):

#include <algorithm>
#include <iostream>
#include <list>
#include <numeric>
#include <random>
#include <vector>
 
int main()
{
    std::list<int> l(10);
    std::iota(l.begin(), l.end(), -4);
 
    std::vector<std::list<int>::iterator> v(l.size());
    std::iota(v.begin(), v.end(), l.begin());
 
    std::shuffle(v.begin(), v.end(), std::mt19937{std::random_device{}()});
 
    std::cout << "Contents of the list: ";
    for(auto n: l) std::cout << n << ' ';
    std::cout << '\n';
 
    std::cout << "Contents of the list, shuffled: ";
    for(auto i: v) std::cout << *i << ' ';
    std::cout << '\n';
}

Instead of shuffling the list directly, a vector of iterators (with a std::vector indices woud work as well) is shuffled and std::shuffle only needs to swap iterators (/indices) rather than the more costly actual elements (in the example the "costly to swap" elements are just ints).

For a std::list I don't expect a big difference between iterating in order or iterating via shuffled iterators. On the other hand, for a std::vector I do expect a significant impact. Hence, I would shuffle indices, then rearrange the vector once, and profile to see which performs better.

---

PS: As noted in comments, std::shuffle is already the optimal algorithm to shuffle a range of elements. However, note that it swaps each element twice on average (possible implementation from cppreference):

for (diff_t i = n-1; i > 0; --i) {
        using std::swap;
        swap(first[i], first[D(g, param_t(0, i))]);

On the other hand, shuffling the indices and then rearranging the vector only requires to copy/move each element once (when additional memory is available).

C++ - Shuffling a vector of objects

deck.reserve(deckSize);

That doesn't add any elements to your vector, it only reserves space for them. So the size of your vector is zero, and when you shuffle it, nothing happens. The rest of your constructor, which sets (non-existent) elements of the vector, as well as your printDeck function, are both undefined behavior. Use resize instead.

deck.resize(deckSize);

In fact, it would be better to just remove the deckSize variable altogether, and just use deck.size().

How can I shuffle a vector with unique pointers in a random sequence with std::shuffle?

std::shuffle() expects random access iterator as std::vector has. You have to replace std::list with std::vector.

clarification regarding std::random_shuffle to shuffle the vector

The function std::random_shuffle has two overloads. In short, that means you can call the same function with a different number of parameters.

• The version std::random_shuffle(vector.begin(), vector.end()); calls an internal random generator which is defined by the implementation (compiler, operative system, standard libraries, ...). However, often it is internally used std::rand.

From the documentation:

The random number generator is implementation-defined, but the function std::rand is often used.

• The version std::random_shuffle(cards_vector.begin(), cards_vector.end(), myrandom); uses an explicit random generator (that you define; that is, myrandom) which internally calls std::rand.

The function std::rand (from C) generate a pseudo-random number. It means that once you have set the seed it will generate (every time) the same number sequence. In other words, the sequence is deterministic depending on the initial value (called seed).

In order to set the seed (the initial value) for the std::rand you need to call the function std::srand which accepts the seed as argument.

The statement srand(time(NULL)); is an old common trick to initialize the generator with a "random" (not actually) seed. Indeed, the function time(NULL) returns the current time which is supposed to be different every time is called.

Therefore, every time your program starts you set the seed with a different number and the generator std::rand will produce a difference sequence every time.

---

Please Note That: std::random_shuffle is an old C++ function and it has been deprecated. You should indeed use its replacement, that is, std::shuffle.

However, the solution above always return the same shuffle, even when the random seed is called in main. I am not sure whether that is intended or not.

The rationale behind this is the same as above.

In that example you are using another (different from std::rand) pseudo-random number generator, that is std::default_random_engine{}. This generator is defaulted initialized with a default seed.

If you want to generate different results for different application run, you need to initialize the generator with a seed which is meant to be different every time your application starts.

A more correct code would be:

#include <algorithm>
#include <chrono>
#include <random>

// ...

auto rng = std::default_random_engine{std::chrono::system_clock::now().time_since_epoch().count()};

Shuffle 2D vector by column

One way is to shuffle each inner vector with the same "random" engine

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

int main()
{
   std::vector<std::vector<int>> v { {1,4,7}, {2,5,8}, {3,6,9} };

   for (int i = 0; i < 3; i++) {
       for (int j = 0; j < 3; j++) {
           std::cout << v[i][j] << " ";
       }
       std::cout << std::endl;
   }
   std::cout << std::endl;

   unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
   for (auto &inner : v) {
      shuffle(inner.begin(),inner.end(), std::default_random_engine(seed));
   }

   for (int i = 0; i < 3; i++) {
       for (int j = 0; j < 3; j++) {
           std::cout << v[i][j] << " ";
       }
       std::cout << std::endl;
   }

   return 0;
}

---

Related Topics