algorithm - what is the most efficient way to pick a random card from a deck when some cards are unusable?

Question

I have an array which tells whether a card is in use:

int used[52];

This is a terrible way to pick a random card if I have many used cards:

do {
  card = rand() % 52;
} while (used[card]);

since if I have only 3-4 unused cards, it'll take forever to find them.

I came up with this:

 int card;
 int k = 0;
 int numUsed = 0;
 for (k=0; k < 52; ++k) {
   if (used[k]) numUsed += 1;
 }
 if (numUsed == 52) return -1;
 card = rand() % (52 - numUsed);

 for (k=0; k < 52; ++k) {
   if (used[k]) continue;
   if (card == 0) return k;
   card -= 1;
 }

which I guess works better if the deck is full, but works worse when the deck is empty since I have to go through two for loops.

What's the most efficient way to do this?

Answer 1

Why don't you just keep another collection of unused cards?

If you want them in random order, you can first shuffle them (Fisher-Yates), then pop them off as you need them.