algorithm - 当某些卡片无法使用时，从卡组中随机挑选一张卡片的最有效方法是什么？

我有一个数组，它告诉你一张卡是否正在使用：

int used[52];

如果我有很多用过的卡，这是一个很糟糕的随机选择卡的方法：

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

因为如果我只有3-4张没用的卡，那就要花很长时间才能找到。
我想到了这个：

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

我想如果甲板是满的，效果会更好，但是如果甲板是空的，效果会更糟，因为我必须通过两个for循环。
最有效的方法是什么？

最佳答案

我认为你的两张牌的算法可能是你能做的最好的，考虑到你在评论中添加的限制，你事先不知道哪些牌有资格抽到一张牌。
你可以尝试一种巧妙的“从未知大小的列表中随机选择”算法：

int sofar = 0;
int selected = -1;
for (i = 0; i < 52; ++i) {
    if (used[i]) continue;
    ++sofar;
    if ((rand() % sofar) == 0) selected = i;
}
if (selected == -1) panic; // there were no usable cards
else used[selected] = 1;   // we have selected a card

然后，如果（如您在注释中所说）不同的绘图具有不同的条件，则可以将used[i]替换为任何实际条件。
其工作方式是选择第一张卡。然后用概率为1/2的第二张卡替换它。将结果替换为概率为1/3的第三张卡片等。通过归纳很容易证明，经过n个步骤后，前面每一张卡片被选中的概率为1/n。
这个方法使用了很多随机数，所以它可能比两次通过的版本慢，除非获取每一项都很慢，或者评估标准很慢它通常用于从一个文件中选择一个随机行，在这里你真的不想在数据上运行两次。它对随机数的偏差也很敏感。
不过，这很好也很简单。
[编辑：证据
设p（j，k）为步骤k之后卡号j是当前选择的卡的概率。
需要证明：对于所有n，p（j，n）=1/n对于所有1对于n=1，很明显p（1，1）=1，因为第一张卡片是在第一步选择的，概率为1/1=1。
假设p（j，k）=1/k，对于所有1然后在步骤（k+1）中选择第（k+1）张卡，概率为1/（k+1），即p（k+1，k+1）=1/（k+1）。
我们保留概率k/（k＋1）的现有选择，因此对于任何j＜k+ 1：

p(j,k+1) = p(j,k) * k/(k+1)
         = 1/k    * k/(k+1)   // by the inductive hypothesis
         = 1/(k+1)

所以p（j，k+1）=1/（k+1），对于所有1因此，通过归纳，对于所有n:p（j，n）=1/n对于所有1