fbpx

C++: Knuth Shuffle

Bjarne-stroustrup
 


Implement the Knuth shuffle (a.k.a. the Fisher-Yates shuffle) for an integer array (or, if possible, an array of any type). The Knuth shuffle is used to create a random permutation of an array.

#include <cstdlib>
#include <algorithm>
#include <iterator>
 
template<typename RandomAccessIterator>
void knuthShuffle(RandomAccessIterator begin, RandomAccessIterator end) {
  for(unsigned int n = end - begin - 1; n >= 1; --n) {
    unsigned int k = rand() % (n + 1);
    if(k != n) {
      std::iter_swap(begin + k, begin + n);
    }
  }
}

The standard library provides this in the form of std::random_shuffle.

#include <algorithm>
#include <vector>
 
int main()
{
    int array[] = { 1,2,3,4,5,6,7,8,9 }; // C-style array of integers
    std::vector<int> vec(array, array + 9); // build STL container from int array
 
    std::random_shuffle(array, array + 9); // shuffle C-style array
    std::random_shuffle(vec.begin(), vec.end()); // shuffle STL container
}

SOURCE

Content is available under GNU Free Documentation License 1.2.