当一些卡片无法使用时,从牌组中挑选随机卡的最有效方法是什么？

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)是在步骤k之后卡号j是当前选择的卡的概率.

需要证明:对于所有n,p(j,n)= 1/n对于所有1 <= j <= n

对于n = 1,显然p(1,1)= 1,因为在第一步选择第一张卡的概率为1/1 = 1.

假设对于所有1 <= j <= k,p(j,k)= 1/k.

然后我们在步骤(k + 1)中以概率1 /(k + 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)

因此,通过归纳,对于所有1的所有n:p(j,n)= 1/n <= j <= n]

Answer 2

你为什么不保留另一张未使用的卡片？

如果你想按随机顺序排列它们,你可以先将它们洗牌(Fisher-Yates),然后根据需要弹出它们.

Answer 3

执行此操作的最佳方法是将套牌随机排序,然后选择第一张未使用的卡片. 以下是执行此类随机播放的最常用方法.