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;
}