随机数和洗牌算法

原文链接：https://coderscat.com/random-number-and-card-shuffling-algorithm

随机数代表不确定性，在计算机领域有着广泛的应用，例如加密密钥生成、密码生成、模拟和游戏。一些经典的随机算法（例如蒙特卡洛算法）也依赖于随机数生成。

在这篇文章中，我们将讨论随机数是如何生成的，以及如何使用随机数来洗牌。

随机数生成

实际上，如果我们只想通过计算机生成随机数，会遇到一些困难。

计算机擅长执行确定性任务，并根据程序运行编码指令。

计算机生成的随机数有两种类型：真随机数和伪随机数，两者各有优缺点。

伪随机数生成器（PRNG）

顾名思义，伪随机数在严格的数学意义上并不是真正的随机数，它通常是由一些数学公式（或计算表）生成的。

例如，可以使用简单的线性同余生成器来生成伪随机数。

我们来看看 Borland 的随机数生成器：

long long RandSeed = 0xdeadbeaf ; // initialize a random seed
unsigned long Random(long max)
{
    long long x ;
    double i ;
    unsigned long final ;
    x = 0xffffffff;
    x += 1 ;

    RandSeed *= ((long long)134775813);
    RandSeed += 1 ;
    RandSeed = RandSeed % x ;
    i = ((double)RandSeed) / (double)0xffffffff ;
    final = (long) (max * i) ;

    return (unsigned long)final;
}

请注意，RandSeed每一代都会更新。

伪随机数生成器（PRNG）的结果在统计学意义上是随机的。伪随机数的行为是可预测的，这意味着如果我们知道PRNG的状态，我们就可以得到下一个随机数。

此外，伪随机数可能具有固定的周期。例如，以下两张位图分别由Windows系统下的实随机数生成器和PHP伪随机数生成器生成。右侧由伪随机数生成器生成的位图呈现出明显的规律。

由于上述特性，伪随机数生成器的使用受到限制，它主要应用于模拟等程序中。

真随机数生成器（RNG）

“真正的”随机数生成器（RNG）通过向计算机引入一些非常不可预测的物理噪声，例如键盘敲击和鼠标移动，来生成随机数。这被称为entropy混沌随机数生成器。真正的随机数难以预测，或者说根本无法预测。

每个操作系统的实现方式都不同。在 Linux 系统中，所有随机性的根源都叫做kernel entropy pool……

例如，MAC地址可用于初始化熵池，其他随机源包括中断时间、硬盘寻址时间等。

这些接口包括 `get_random_bytes` /dev/random、 `get_random_bytes`/dev/urandom和`get_random_bytes`，其中 `get_random_bytes` 在内核中使用。`get_random_bytes`和`get_random_bytes`get_random_bytes()的区别在于，` get_random_bytes`更强大且阻塞，因为它收集了更多的熵。/dev/random/dev/urandom/dev/random

随机数的使用

涉及随机数的程序需要格外小心。

例如，我们来编写一个简单的程序。

我们知道 C 语言中 rand() 函数生成的随机数有一个范围0~32767，如何编写一个函数来生成该范围内的随机数0~10？

或许你会直接给出解决方案：（rand()%10我也用过这个方法），但这真的是随机的吗？

如果将从 0 到 32767 的所有数字进行运算%10，你会发现有些数字出现的频率更高，因此某些数字出现在末尾的概率也相应更大。

洗牌算法

编写一个合适的洗牌程序看似容易，实则不然。

如果你要运营线上扑克，这种情况发生起来确实很棘手。如果你宣传会进行随机洗牌，那就一定要确保真的这么做。

——罗伯特·塞奇威克，计算机科学教授

ASF Software 多年前编写了一款流行的在线扑克游戏，其中的洗牌程序是以下 Pascal 代码：

procedure TDeck.Shuffle;
var
   ctr: Byte;
   tmp: Byte;
   random_number: Byte;
begin
   { Fill the deck with unique cards }
   for ctr := 1 to 52 do
      Card[ctr] := ctr;
   { Generate a new seed based on the system clock }
   randomize;
   { Randomly rearrange each card }
   for ctr := 1 to 52 do begin
      random_number := random(51)+1;
      tmp := card[random_number];
      card[random_number] := card[ctr];
      card[ctr] := tmp;
   end;
   CurrentCard := 1;
   JustShuffled := True;
end;

让我们简化一下核心的洗牌算法（注意，在 Pascal 中数组的索引从 1 开始）：

for (i is 1 to N)
  j = random integer that 1 <= j <= N
  Swap a[i] with a[j]

这里的洗牌算法存在问题。52!不同排列的概率各不相同。

我们以三张卡片 1、2、3 为例，以下是 3 次迭代后的结果：

我们可以看到231，，，出现213的132频率更高，因此相应的概率也更大。

正确的洗牌算法是，即Fisher-Yates算法：

for (i is 1 to N)
  j = random integer that i <= j <= N
  Swap a[i] with a[j]

另一个可能难以发现的问题是，使用 32 位数字作为种子对于伪随机数生成器来说是有问题的，因为给定伪随机数生成器的行为是可预测的。

种子为 32 位时，可能的值的数量是2^32，远小于52!(8.0658 * 10^67)。因此，对于 32 位种子，甚至可以使用暴力破解法来破解。

给你一些与随机数相关的练习

1. 生成一个范围内的随机数

给定一个rand()可以生成介于 [1, 7] 之间的随机整数的函数[1, 5]，如何使用该函数生成介于 [1, 7] 之间的随机整数？

2. 彩票计划

编写一个抽奖程序，从 30 万用户中随机选出 10 万名中奖用户？

3. 平均工资（开放式问题）

10个人围坐在一张桌子旁，他们想知道平均年薪，但每个人都不愿意向别人透露自己的薪水。

有没有办法既能得到答案，又不泄露任何人的薪资信息？

参考

维基百科：随机数生成。
我们如何学会在线扑克作弊：软件安全研究。
罗伯特·塞奇威克的算法。
如何随机化（洗牌）JavaScript 数组？