首先，这个问题取自于这个问题。我这样做是因为我认为这部分比长问题的子部分更重要。如果有冒犯之处，请见谅。
假设你有一个生成随机数的算法。那么你如何测试它呢？ 或者更直接地说——假设你有一个洗牌算法，那么怎么测试它是完全随机的算法呢？
为了给问题加点理论背景——一副牌可以按52!（52的阶乘）种不同的方式洗牌。拿一副牌，手动洗牌并记录所有牌的顺序。你得到刚好那个顺序的概率是多少？答案是：1 / 52!。
在洗牌后，你得到每个花色的A、K、Q、J……连续排列的机会是多少？答案是 1 / 52!。
因此，仅仅洗牌一次然后观察结果对于判断洗牌算法的随机性没有任何信息价值。两次洗牌获得更多信息，三次甚至更多……
你会如何对一个洗牌算法进行黑盒测试以确定其随机性？
统计学。 在测试随机数生成器方面，事实上的标准是Diehard套件（最初在http://stat.fsu.edu/pub/diehard上提供）。 或者，Ent程序提供的测试更简单易懂，但不太全面。
至于洗牌算法，请使用众所周知的算法，如Fisher-Yates（又称“Knuth Shuffle”）。 只要底层随机数生成器是均匀随机的，洗牌就会均匀随机。 如果您使用的是Java，此算法可以在标准库中找到（请参见Collections.shuffle）。
对于大多数应用程序来说可能并不重要，但是请注意，大多数随机数生成器无法提供足够的自由度来产生52张纸牌的每个可能的排列（解释在此处）。
/**
* This is a rudimentary check to ensure that the output of a given RNG
* is approximately uniformly distributed. If the RNG output is not
* uniformly distributed, this method will return a poor estimate for the
* value of pi.
* @param rng The RNG to test.
* @param iterations The number of random points to generate for use in the
* calculation. This value needs to be sufficiently large in order to
* produce a reasonably accurate result (assuming the RNG is uniform).
* Less than 10,000 is not particularly useful. 100,000 should be sufficient.
* @return An approximation of pi generated using the provided RNG.
*/
public static double calculateMonteCarloValueForPi(Random rng,
int iterations)
{
// Assumes a quadrant of a circle of radius 1, bounded by a box with
// sides of length 1. The area of the square is therefore 1 square unit
// and the area of the quadrant is (pi * r^2) / 4.
int totalInsideQuadrant = 0;
// Generate the specified number of random points and count how many fall
// within the quadrant and how many do not. We expect the number of points
// in the quadrant (expressed as a fraction of the total number of points)
// to be pi/4. Therefore pi = 4 * ratio.
for (int i = 0; i < iterations; i++)
{
double x = rng.nextDouble();
double y = rng.nextDouble();
if (isInQuadrant(x, y))
{
++totalInsideQuadrant;
}
}
// From these figures we can deduce an approximate value for Pi.
return 4 * ((double) totalInsideQuadrant / iterations);
}
/**
* Uses Pythagoras' theorem to determine whether the specified coordinates
* fall within the area of the quadrant of a circle of radius 1 that is
* centered on the origin.
* @param x The x-coordinate of the point (must be between 0 and 1).
* @param y The y-coordinate of the point (must be between 0 and 1).
* @return True if the point is within the quadrant, false otherwise.
*/
private static boolean isInQuadrant(double x, double y)
{
double distance = Math.sqrt((x * x) + (y * y));
return distance <= 1;
}
isInQuadrant() 中不需要使用 Math.sqrt()。 - jfs有很多关于测试随机性的理论。对于一个非常简单的卡牌洗牌算法测试，您可以进行大量的洗牌，然后运行卡方检验，以确保每张卡牌出现在任何位置的概率是均匀的。但这并不能测试连续的卡牌是否相关，因此您还需要进行相关测试。
Knuth的《计算机程序设计艺术》第2卷在3.3.2节（经验测试）和3.3.4节（频谱测试）中给出了许多可用的测试及其背后的理论。
大量洗牌，然后记录结果（如果我理解正确的话）。我记得看到过“随机数生成器”的比较。他们只是一遍又一遍地测试，然后绘制图表显示结果。
如果它真的是随机的，那么图表应该基本上是均匀的。
目前还没有代码，因此我从我的回答中复制粘贴了一个测试部分到原始问题中。
// ...
int main() {
typedef std::map<std::pair<size_t, Deck::value_type>, size_t> Map;
Map freqs;
Deck d;
const size_t ntests = 100000;
// compute frequencies of events: card at position
for (size_t i = 0; i < ntests; ++i) {
d.shuffle();
size_t pos = 0;
for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos)
++freqs[std::make_pair(pos, *j)];
}
// if Deck.shuffle() is correct then all frequencies must be similar
for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j)
std::cout << "pos=" << j->first.first << " card=" << j->first.second
<< " freq=" << j->second << std::endl;
}
这段代码并不测试底层伪随机数生成器的随机性。测试PRNG的随机性是整个科学领域的一个分支。
对于快速测试，您可以尝试压缩它。一旦无法压缩，那么您可以进行其他测试。
我已经尝试了dieharder，但它拒绝为洗牌工作。所有测试都失败了。它也非常呆板，不允许您指定所需值的范围或类似的任何内容。
我不完全理解你的问题。你说：
假设您有一个生成随机性的算法。现在该如何测试它？
您是什么意思？如果您认为您可以生成随机性，那么就没有必要进行测试。
一旦您拥有了一个好的随机数生成器，创建随机排列就很容易了（例如：将您的牌命名为1-52。生成52个随机数，将每个随机数分配给一张牌，并按照您的52个随机数进行排序）。通过生成排列，您不会破坏您的好RNG的随机性。
困难的问题是您是否可以信任您的RNG。 这是一个讨论特定情境中这个问题的样例链接。
当然，测试52！种可能性是不可能的。相反，尝试在较少的牌数上进行洗牌，比如3、5和10张牌。然后，您可以测试数十亿次洗牌，并使用直方图和卡方统计检验来证明每个排列出现的次数是“均匀”的。