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

Question

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

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循环。

最有效的方法是什么？

Answer 1

我认为您的两遍算法可能是您最好的选择，因为您在注释中添加了约束，而您事先并不知道哪些卡适合进行给定抽奖。

您可以尝试狡猾的“单次通过从未知大小的列表中随机选择”算法：

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）为卡号j为步骤k之后当前选择的卡的概率。

需要证明：对于所有n，对于所有1 <= j <= n，p（j，n）= 1 / n

对于n = 1，显然p（1,1）= 1，因为在第一步以概率1/1 = 1选择了第一张牌。

假设所有1 <= j <= k的p（j，k）= 1 / k。

然后，我们在步骤（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)

所以对于所有1 <= k <= k + 1，p（j，k + 1）= 1 /（k + 1）

因此，通过归纳，对于所有n：对于所有1 <= j <= n]，p（j，n）= 1 / n