2

假设我们要编写一个方法来产生一副洗牌的纸牌。现在让它变得非常简单，忽略花色，所以我们有 52 张牌。

一种算法是：

  • 填充一个包含 52 个元素的数组，其中第一个元素为 1，第二个元素为 2，依此类推。
  • 编写一个迭代 X 次的 for 循环，在每次迭代期间，随机选择两张牌并交换它们。
  • X 越大，洗牌越随机。

另一种算法：

  • 像以前一样填充数组。
  • 编写一个迭代 26 次的 for 循环，并在每次迭代期间选择两个随机数并将这两个数字放在另一个 52 元素数组的连续前面，该数组存储新选择的数字。
  • 在每次迭代中，从原始数组中删除添加到新数组中的两张卡片。

我知道有更好的洗牌算法，但是关于这两个，哪一个更好，为什么？

4

4 回答 4

1

第二种算法似乎是Fisher-Yates的一个展开的两个实现。这种洗牌具有选择具有均匀分布的所有可能结果之一的特性。大多数人称之为“公平”或“完美”的洗牌。只要您的随机数生成器提供无偏的结果，就无需重复该操作以获得额外的随机性。

第一个算法可能会渐近地接近我不知道什么类型的分布。出于各种原因，我会避免它。主要是因为我不知道 X 需要多大才能产生良好的 shuffle，但我确信它超过 52。除了故意模拟不充分的 shuffle 之外，我想不出这个算法的好应用。

第一个算法正在工作，这在某些情况下是有益的，但如果你想要，那么你可以修改第二个算法以类似的方式运行。

于 2013-05-31T19:22:23.003 回答
1

您必须定义“更好”的含义。第一种算法的问题在于，某些元素可能永远不会改变位置。例如，如果您从不随机获得低数字，则第一张牌将按顺序排列。

第二种算法会让你更加随机化。但是，如果您只运行一次，那么项目将可能在它们的最终位置是可预测的。

我会多次运行算法 2，或者像你做真正的牌组一样洗牌

1: Split the deck into two arrays of 26
2: Take the top card from one of the arrays at random and put it into a new array of size 52
3: Keep doing this until one array is empty, put the remaining cards of the other array into the size 52 array
4: Repeat

这将为您带来很好的随机化

于 2013-05-31T19:02:14.357 回答
1

第一个算法产生高度偏差的分布，因为它可能会在初始位置留下一些卡片并且容易受到“双重交换”问题的影响（交换相同的两张卡片两次导致初始卡片状态）。

第二种算法，正如@sh1 提到的，是Fisher-Yates 算法的展开版本，有一个小例外：它不再是线性的，因为从列表中删除项目本身就是线性操作，并且在每次迭代时执行，因此整体算法复杂度是O(n^2)。

Fisher-Yates 算法的有效版本如下：

在伪代码中（因为你没有提到选择的语言）

for i from n − 1 downto 1 do
   j ← random integer with 0 ≤ j ≤ i
   exchange a[j] and a[i]

和python实现，以防万一:)

import random
n = 52
arr = [i for i in range(1,n+1)]

for i in range(n-1, 1, -1):
    elem_to_swap = random.randint(0, i)
    arr[elem_to_swap], arr[i] = arr[i], arr[elem_to_swap]
于 2013-05-31T19:41:30.700 回答
0

更好的是：

  1. 在某个临时数组中生成 52 个数字
  2. 使用临时数组作为键对带有卡片的数组进行排序

在 C# 中它看起来

Random r = new Random(DateTime.Now.Miliseconds);
string [] cards = new string[52]{"1","2",.....};
int [] temp = new int[52];
for(int i=0;i<52;i++)
{
    temp[i]=r.Next();
}

Array.Sort(temp,cards);
于 2013-05-31T18:59:42.407 回答