3

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

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

最有效的方法是什么？

4

9 回答 9

10

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

如果您希望它们以随机顺序排列，您可以先将它们洗牌（Fisher-Yates），然后根据需要将它们弹出。

于 2009-07-15T20:53:00.957 回答
10

我认为你的两遍算法可能是你能做的最好的，考虑到你在评论中添加的限制，你事先不知道哪些卡有资格进行给定的平局。

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

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)

所以 p(j,k+1) = 1/(k+1) 对于所有 1 <= k <= k+1

因此，通过归纳，对于所有 n： p(j,n) = 1/n for all 1 <= j <= n]

于 2009-07-15T21:47:12.190 回答
6

最好的方法是将牌组随机洗牌，然后选择第一张未使用的牌。 这是执行此类随机播放的最常见方法。

于 2009-07-15T20:53:48.990 回答
2

随机发牌的标准算法是。

  • 初始化卡片组以包含所有卡片（顺序不重要）
  • 环形：
  • 生成范围为 0 到 deck-size - 1 的随机索引
  • 在该索引处显示卡（或做任何你想做的事）
  • 将卡片组中的索引卡片与 [卡片组大小 -1] 的卡片交换
  • 将甲板尺寸减少一
  • goto 循环：根据需要经常
于 2009-07-15T20:58:02.100 回答
1

您可以使用以下代码摆脱这两个循环：

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

虽然我想效率的提高不会很大，而且你会使用更多的内存。

于 2009-07-15T20:58:52.537 回答
1

另一种选择是有两个列表，一个用来跟踪用过的卡片，一个用来跟踪未使用的卡片。因此，如果您使用卡片，请将其从未使用的卡片列表中减去并将其添加到已使用卡片列表的末尾。这样，您就不必每次都运行两个 for 循环。

于 2009-07-15T21:02:51.950 回答
0

将使用过的卡片放在阵列的末尾，将未使用的卡片放在开头。跟踪有多少卡尚未使用。使用新卡时，将其与最后一张未使用的卡交换并减少剩余卡的数量。

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--;
于 2009-07-15T21:59:00.013 回答
0

多种语言的 Knuth Shuffle

于 2009-07-16T05:06:40.623 回答
-1

我不确定这是否会产生真正的随机抽签，但在几乎所有情况下，它都会避免整个牌组的循环。我什至不太确定它将如何比较性能，但仍然如此：

  • 从牌组中随机获得一张牌
  • 如果卡已被使用，选择一个随机方向（向前或向后）
  • 从当前位置沿随机确定的方向穿过牌组，直到找到下一张未使用的牌（当然，您必须确保在阵列末端正确环绕）

因此，在最坏的情况下，您在最后一张未使用的牌旁边选择一张牌，然后以“错误”的方向穿过牌组，从而在牌组中执行完整的循环。

于 2009-07-16T05:38:12.180 回答