Fisher-Yates modern shuffle algorithm

Question

I have implemented the shuffling algorithm of Fisher-Yates in C++, but I've stumbled across the modulo bias. Is this random number generation by rand() correct for Fisher-Yates?

srand(time(NULL));
vector<int> elements;
// push numbers from 1 to 9 into the vector
for (int i = 1; i < 9; ++i)
{
    elements.push_back(i);
}

// the counter to be used to generate the random number
int currentIndexCounter = elements.size();
for (auto currentIndex = elements.rbegin(); currentIndex != elements.rend() - 1;
     currentIndex++ , --currentIndexCounter)
    {
        int randomIndex = rand() % currentIndexCounter;
        // if its not pointing to the same index      
        if (*currentIndex != elements.at(randomIndex))
        {
            //then swap the elements
            swap(elements.at(randomIndex), *currentIndex);
        }
    }

Answer 1

@Loki Astari is correct in his comment:

rand() is well know for its bad distribution. But you are using it correctly. Note: rand() % currentIndexCounter does not give you a perfect distribution unless currentIndexCounter is an exact divisor of RAND_MAX. You may want to look at C++11 random header and the generators provided inside.

Since you're using C++11, you should instead utilize the <random> library. It includes things such as pseudo-random number generators and random number distributions.

---

Beyond that, I'll just point out some additional things:

• With C++11, you should now be using nullptr instead of NULL.

  This should be changed in srand():

  std::srand(std::time(nullptr));
  

  However, as mentioned above, you should not be using this with C++11. But in any situation where you must stay with rand, the above would be recommended.

• With C++11, you should also have access to initializer lists. This will allow you to initialize the vector instead of calling push_back() multiple times:

  std::vector<int> elements { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  

  Also note that your push_back() was only pushing numbers 1-8 into the vector, despite what your comment said. You've used < instead of <= in the loop statement, so the 9 was excluded.

• currentIndexCounter should be of type std::vector<int>::size_type, which is the return type of size() (or you can just use auto). This should've given you compiler warnings as it's a type-mismatch and a possible loss of data. Make sure your compiler warnings are turned up high.

• currentIndex is a misleading name because it's being used with iterators, not indices.

  Here, auto gives currentIndex the type std::reverse_iterator from std::rbegin(). You could simply name this something like iter. It's okay for iterator names to be short.

• In the second for loop, you just need elements.rend(), without the - 1. The iterator will already go through the entire vector and stop at the last reverse element.

• The iterator increment should be prefix instead in order to improve performance a bit by avoiding a copy. It's best to do this with all nontrivial types such as iterators.

• I've tested this by giving randomIndex a value greater than elements.size(), causing an exception to be thrown. Even if std::rand() or another RNG is guaranteed to give you an intended value, it may be best to handle this properly.

Here's the final version with my own given changes, which I've also ran here. I've also included a concise way of displaying the vector before and after the shuffling.

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

int main()
{
    // seed the RNG
    std::random_device rd;
    std::mt19937 mt(rd());

    std::vector<int> elements { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    std::cout << "Before: ";
    std::copy(elements.cbegin(), elements.cend(),
        std::ostream_iterator<int>(std::cout, " "));

    auto currentIndexCounter = elements.size();

    for (auto iter = elements.rbegin(); iter != elements.rend();
        ++iter, --currentIndexCounter)
    {
        // get int distribution with new range
        std::uniform_int_distribution<> dis(0, currentIndexCounter);
        const int randomIndex = dis(mt);

        if (*iter != elements.at(randomIndex))
        {
            std::swap(elements.at(randomIndex), *iter);
        }
    }

    std::cout << "\nAfter: ";
    std::copy(elements.cbegin(), elements.cend(),
        std::ostream_iterator<int>(std::cout, " "));
}

Output:

Before: 1 2 3 4 5 6 7 8 9
After: 7 9 3 2 4 5 6 1 8

Answer 2

Here is my take on it with the modern <random>:

static const void fisher_yates_shuffle(std::deque<card>& cards)
{
  std::random_device                          random                    ;
  std::mt19937                                mersenne_twister(random());
  std::uniform_int_distribution<std::uint8_t> distribution              ;
  for (auto i = cards.size() - 1; i > 0; --i)
  {
    distribution.param(std::uniform_int_distribution<std::uint8_t>::param_type(0, i));
    std::swap(cards[i], cards[distribution(mersenne_twister)]);
  }
};