我有一个数组，告诉是否正在使用卡：
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]实际的条件代替。
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
