Shuffle

17.2 Shuffle: Write a method to shuffle a deck of cards. It must be a perfect shuffle-in other words, each of the 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect.
  • I could just create a new deck where each card I take from the deck has the same probability of being chosen.
    • First selection: 1/52
    • Second selection: 1/51 ...
  • std already has a shuffle method. In my implementation, I iterate through the deck of cards and swap with any random position, all with equivalent likelihood.
void swap(int *a, int *b) {
int temp = *(a);
*(a) = *(b);
*(b) = temp;
}
void shuffle(array<int, 52> &deck) {
int r;
for (int i = 0; i < deck.size(); i++) {
r = rand() % 52;
swap(deck[i], deck[r]);
}
}
int main()
{
srand(time(nullptr));
array<int, 52> deck;
for (int i = 0; i < deck.size(); i++) {
deck[i] = i;
}
//random_shuffle(deck.begin(), deck.end());
//for (auto i : deck) {
// cout << i << " ";
//}
//cout << endl;
shuffle(deck);
for (auto i : deck) {
cout << i << " ";
}
cout << endl;
}