Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is this C implementation of Fisher-Yates shuffle correct?

Tags:

c

shuffle

Here's a C implementation of Fisher-Yates that I want to use in a deck-shuffling routine. Am I doing this correctly (n = length of array)?

Note: The do-while loop attempts to correct for the modulo bias (see here). It adds a bit of overhead to the procedure and could be eliminated if you don't care about the low-bit bias.

void shuffle(int *array, int n) {

  int i, j, tmp, upper_bound;

  srand(time(NULL));

  for (i = n - 1; i > 0; i--) {

    upper_bound = RAND_MAX - ((RAND_MAX % (i + 1)) + 1);

    do {
      j = rand() % (i + 1);
    } while (j > upper_bound);

    tmp = array[j];
    array[j] = array[i];
    array[i] = tmp;   
  }
}
like image 509
MikeRand Avatar asked Jul 27 '10 12:07

MikeRand


People also ask

How does the Fisher Yates shuffle work?

The Fisher–Yates shuffle, as implemented by Durstenfeld, is an in-place shuffle. That is, given a preinitialized array, it shuffles the elements of the array in place, rather than producing a shuffled copy of the array. This can be an advantage if the array to be shuffled is large.

What is the running time of Fisher Yates algorithm?

The time complexity of this solution will be O(n^2). Fisher–Yates shuffle Algorithm works in O(n) time complexity. The assumption here is, we are given a function rand() that generates a random number in O(1) time.

How do you shuffle an array in C++?

Shuffle an Array using STL in C++ These are namely shuffle() and random_shuffle(). This method rearranges the elements in the range [first, last) randomly, using g as a uniform random number generator. It swaps the value of each element with that of some other randomly picked element.


1 Answers

First, you should extract the code for generating a random number that's equally distributed between 0 (inclusive) and n (exclusive) to a separate function. That's a nice task of work that you will need elsewhere, too.

Second, I would not call srand inside the shuffle function but depend on the caller on initializing the random number generator. That way you can shuffle a deck more than once in a second.

Third, you should do the test for j > upper_bound before dividing by i + 1. It's unlikely that i will ever be near RAND_MAX.

static int rand_int(int n) {
  int limit = RAND_MAX - RAND_MAX % n;
  int rnd;

  do {
    rnd = rand();
  } while (rnd >= limit);
  return rnd % n;
}

void shuffle(int *array, int n) {
  int i, j, tmp;

  for (i = n - 1; i > 0; i--) {
    j = rand_int(i + 1);
    tmp = array[j];
    array[j] = array[i];
    array[i] = tmp;
  }
}

To check whether this implementation may be correct, you need to ensure that you asked the random number generator for log2(n!) bits of randomness. In other words, the product of all the ns given to the rand_int function must be n!.

like image 94
Roland Illig Avatar answered Nov 16 '22 04:11

Roland Illig