Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
673 views
in Technique[技术] by (71.8m points)

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

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?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...