什么是最有效的方式，从一副扑克牌中随机选择一个卡时，有些卡是不能使用？(what is the mo

我有一个数组，其讲述了一个卡是否正在使用：

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，P（J，N）= 1 / n，用于所有1 <= j的<= N

对于n = 1，显然P（1,1）= 1，由于第一卡在与概率1/1 = 1在第一步骤中选择。

假设P（J，K）= 1 / K对于所有1 <= j的<= K。

然后，我们的概率是1 /（K + 1），即，p选择第（k + 1）个卡在步骤（k + 1）（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 <= K <= K + 1

因此，通过感应，对于所有的N：P（J，N）= 1 / n的所有1 <= j的<= N]

Answer 2:

你为什么不只是不停的未使用的卡的另一个集合？

如果你希望他们以随机顺序，可以先打乱他们（费雪耶茨），然后弹出它们赶走，你需要他们。

Answer 3:

要做到这一点，最好的办法是到甲板洗牌成随机的顺序，然后选择第一个未使用的卡。下面就来进行这样的洗牌最常见的方式。

Answer 4:

用于处理随机卡的标准算法。

初始化甲板包含所有卡（为了不重要的）
环：
产生在范围0到甲板尺寸随机索引 - 1
该指数显示卡（或做任何你想要的）
交换索引在甲板卡与卡在[甲板大小-1]
减少一个甲板尺寸
转到循环：根据需要经常

Answer 5:

你可以摆脱使用类似代码的两个循环：

int card;
int k = 0;
int i = 0;
int unUsed[52];
int numUsed = 0;
for (k = 0; k < 52; ++k) {
  if (used[k]) {
    numUsed += 1;
  } else {
    unUsed[i] = k;
    i++;
  }
}
if (numUsed == 52) return -1;
card = rand() % (52 - numUsed);
return unUsed[card];

虽然我会想象在效率的提高也不会大，并且您将使用更多的内存。

Answer 6:

另一种选择是将有两个列表，使用一种用于跟踪使用的卡和一个跟踪未使用的卡。所以，如果你使用的卡片，从未使用的卡列表中减去它并将其添加到所使用的卡列表的末尾。这样一来，你就不用跑了两个for循环的每一次。

Answer 7:

请用过的卡在开始阵列和未使用的卡的结束。跟踪的多少卡尚未使用。当使用新卡，与上次未使用的卡掉它和递减的剩余的牌数。

if (numRemaining == 0) return -1;
int cardNum = rand() % numRemaining;
Card card = cards[cardNum]; // or int, if cards are represented by their numbers
cards[cardNum] = cards[numRemaining - 1];
cards[numRemaining - 1] = card;
numRemaining--;