这个问题太有创意了。

随机数生成器目前来说，大致分为两类。

第一种，伪随机数。伪随机数是依靠数学算法来实现的，我们常见的 PC，游乐场的抽奖，赌场的赌博机等依赖的都是依据一定算法的伪随机数。这种算法都依赖一串种子，只要种子确定了，我们就可以预测出后面的随机数串，也就说这个不是我们想要的真正的随机数。现在有媒体报道，俄罗斯的黑客以及数学家，就通过破解美国赌场的老虎机的随机数生成器来赚钱。

第二类，物理随机数。其是依靠物理学规律的随机数发生器，比如核衰变发生的时刻，单个光子经过分束器时的选择。只要现有的物理规律是正确的，那么我们就无法预知生成器生成的下一个随机数是什么。其实物理随机数还可以继续细分，有噪声， 混沌，量子随机数发生器，而量子数随机数发生器又可分为：practical random number generator，设备无关随机数发生器等。

结论：地球上的黑客均没有控制到谁死谁活，所以这随机数发生器是物理的，不是伪随机。其次，不惜一切代价忠实地践行自己意志的灭霸同志，应该不会对设备做手脚，所以灭霸使用的可能是量子随机数发生器中的设备无关随机数发生器，这种随机数发生器不以个人意志为转移。

Reference：

1. Herrero-Collantes M, Garcia-Escartin J C. Quantum random number generators[J]. Reviews of Modern Physics, 2017, 89(1): 015004.
2. James F. A review of pseudorandom number generators[J]. Computer physics communications, 1990, 60(3): 329-344.

最近工作实在太忙，一直没有看《复仇者联盟 3》这部电影，所以我还不了解电影的具体情节（虽然我感觉已经被剧透光了，哈哈哈）。不过，听了周围人和知乎上一些答案对灭霸计划的描述后，觉得这道题实在是太有意思了！下面我们来尝试解答一下这个问题。看看可能有哪些方法、又应该用哪些方法满足“不掺杂感情因素，随机地让宇宙里一半人口消失”的宏大伟业吧！

---

随机数的生成机制是什么？

有关这个问题，知友 @Li YaPing 已经做了简单的介绍，我们讲的再详细一点好了。我们可以把现有随机数生成机制分为两大类。

第一种：物理随机数

这是真正从物理现象中采集的随机数。相信知友们都知道“薛定谔的猫”，这就是一个典型的物理随机数：

（来自百度百科：薛定谔的猫）一只猫被封在一个密室里，密室里有食物有毒药。毒药瓶上有一个锤子，锤子由一个电子开关控制，电子开关由放射性原子控制。如果原子核衰变，则放出阿尔法粒子，触动电子开关，锤子落下，砸碎毒药瓶，释放出里面的氰化物气体，猫必死无疑。原子核的衰变是随机事件，物理学家所能精确知道的只是半衰期——衰变一半所需要的时间。如果一种放射性元素的半衰期是一天，则过一天，该元素就少了一半，再过一天，就少了剩下的一半。物理学家却无法知道，它在什么时候衰变，上午，还是下午。

当人类无法预测一些物理现象的发生与否，只知道物理现象发生的统计规律或理论规律，我们就可以利用这些物理现象构造物理随机数。

物理随机数的最大优点是：无法预知下一个随机数是什么。相对地，物理随机数的缺点是：随机数的采集过程相对较为复杂。

第二种：伪随机数

物理随机数的采集代价实在太高，是否能有一些比较简单的随机数生成方法呢？答案是肯定的。沉下心来思考一下就会发现，我们日常生活中需要的可能并不是真正随机的随机数，只要生成的随机数“看起来像是一个随机数”就可以了。我们把能生成“看起来像是一个随机数”的算法称为伪随机数生成器（Pseudo-Random Generator，PRG）。此类算法需要设置一个种子（seed）作为参数。可以把种子理解为算法的初始状态。当种子设置完毕后，持续调用算法即可输出一系列看起来像是随机数的数了。

伪随机数的最大优点是：随机数生成过程非常简单，可以快速得到大量的随机数。相对地，伪随机数的最大缺点是：由于算法以种子作为初始状态，而计算机执行算法的过程一定是确定性的，因此只要能够知道种子是什么，那么伪随机数生成器的输出结果就能看作是随机数了，可以完全实现输出结果的预测和复现。

相信反派用的是物理随机数

既然我们现在讨论的是超级英雄们的故事，连时间倒转都可以做到，因此我们有理由相信在《复仇者联盟》的故事中，反派有能力采集真正的物理随机数。

为了后续论述方便，我们假定反派可以按照现在人类的计算机一样，可以从物理环境中采集到一个结果在

中满足均匀分布的随机数好了。

---

谁执行随机数的生成过程？

无论是谁决定谁生谁死，我们都有理由相信决定前一定不在灭霸本人手中。因为我们的目标是“不掺杂感情因素，随机地让宇宙里一半人口消失”，如果灭霸本人可以提供哪怕一点点谁生谁死的相关信息，那就不满足“不掺杂感情因素”这个前提条件了。以此类推，既然“不掺杂感情因素”，那么这个决定权也一定不在其它任何人手中，只能是一个“完全”随机的过程。既然执行杀戮的“设备”是拳套，我们姑且可以认为是由拳套完成随机数采集，并执行杀戮过程好了。

---

应该使用何种杀人算法

下面我们需要解决的一个问题是：如何利用上述的基础模块，设计一个算法，实现公平的杀人呢？知友们已经提出了很多很有意思的方法。所有方法几乎可以归为下述两种情况：

1. 为每一个生物抛一枚硬币，正面就杀掉，反面就活着；
2. 把所有生物随机拍成一个队列，奇数位置上的生物杀掉，偶数就活着；

下面我们来科学地论述一下，这两种方法到底哪种更好？应该使用哪种方法呢？

随机数所满足的概率分布

在选择方法之前，我们首先需要知道我们需要一个满足什么条件的随机数。计算机所内置的随机数生成器一般都会输出一个结果在

中满足均匀分布的随机数生成器出发。也就是说，计算机中随机数生成器所输出的随机变量所满足的概率密度函数为：

得到这样一个随机数后，我们可以进一步通过数学变换得到概率分布更加复杂的随机数生成算法。上面两种情况都可以用满足此种要求的随机数实现。下面我们一一进行讲解。

抛硬币：看似科学，实则不合理

我们先来看看第一种方法：为每一个生物抛一枚硬币，正面就杀掉，反面就活着。

利用上述随机数是可以做到这种杀戮方法的，具体如下：

• 分别对每一个生物执行随机数生成算法，得到一个结果在 中满足均匀分布的随机数。
• 如果得到的随机数小于 ，则杀掉这个生物，否则此生物存活。

很容易证明，每个生物被杀掉的概率均为，原因是

这似乎满足灭霸的要求。但是，这种方法有一个最大的问题：假定所有生物的数量为?，那么按照这个过程杀戮完毕后，死亡的生物总数量不严格为！这对于作风严谨的灭霸同学，能接受吗？

下面我们来论述一下，死亡的生物总数量应该是多少。我们可以把这个杀人的过程看成放回抽样的过程：对于每一个生物，从一个有??个白球、?个黑球的袋子中取出一个球，如果是黑球就杀掉、白球就或者。抽完球后把球放回口袋。我们要考察当抽出??个球后，抽出黑球个数的概率。在概率论中，抽出黑球的个数??满足参数为??二项分布，或伯努利分布，其概率为：

。我们只知道其期望为?，也就是说死亡生物的数量均值为?。不过，这个随机变量的方差还挺大的，达到?。

对于灭霸这么严谨的人，既然说了“随机地让宇宙里一半人口消失”，那就真应该是让“一半人口消失”，而不是“差不多让一半人口消失”吧…

报数杀人，科学但非最优的杀人方法

沿着上面抽球的思路，我们其实应该这么想：把所有的??个生物都放在一个口袋里面，每次随机从口袋里面取出一个生物后就不放回，抽出??个生物后把抽出来的生物杀掉，口袋中的生物活着。这个过程就变成了一个不放回采样的过程。这样一来，我们既可以保证“随机地让宇宙里的人口消失”，又可以保证“让宇宙里一半人口消失”，似乎这是一个更加科学的方法。

那么，如何通过一系列在??中满足均匀分布的随机数实现上述杀人的方法呢？实际上我们只需要解决一个问题：把所有生物按照 1 到 n 编号，如何从

中随机选出一个编号，把对应编号的人杀掉？只要解决了这个问题，我们就可以持续执行上述过程：

• 把剩余的生物按照 1 到 n-1 编号，随机选出一个编号，把对应编号的人杀掉；
• 把剩余的生物按照 1 到 n-2 编号，随机选出一个编号，把对应编号的人杀掉；
• ......

怎么实现这个过程呢？很简单，得到??中满足均匀分布的随机数后，把随机数乘以 n 后向上取整即可。把随机数乘以 n 后，随机数所满足的概率分布变为：

对结果向上取整后，对于任意?，我们有：

如此一来，灭霸终于可以保证“随机地让宇宙里一半人口消失”这一宏伟的过程了！

Can we do better？洗牌杀戮法

上述杀戮过程虽然不错，但是每一次都要对生物重新编号，似乎有点麻烦，能不能有更简单的方法呢？转换一下思路，如果我们能把所有生物随机进行编号，奇数编号杀掉，偶数编号留着，只要编号过程是完全随机的，是不是就可以实现相同的杀戮要求呢？

这实际上是计算机科学中一个非常经典的问题：洗牌问题（Shuffle A Deck of Cards），要求如下：

（来自Shuffle a given array - GeeksforGeeks）Given an array, write a program to generate a random permutation of array elements. This question is also asked as “shuffle a deck of cards” or “randomize a given array”.

简单的实现方法就是前述的报数杀人法：

A simple solution is to create an auxiliary array temp[] which is initially a copy of arr[]. Randomly select an element from temp[], copy the randomly selected element to arr[0] and remove the selected element from temp[]. Repeat the same process n times and keep copying elements to arr[1], arr[2], … .The time complexity of this solution will be O(n^2).

按照我们的场景描述就是：把所有生物倒在一个袋子 temp 里面，创建空的袋子 arr，从袋子 temp 中随机选择一个生物放在袋子 arr 中，并且从袋子 temp 中把选择出的生物移除。与题目中的要求不同，这里我们只需要从袋子 temp 中随机拿出??个生物即可。不过整个算法所需要进行的操作次数（即算法复杂度）仍然达到 O(n^2)，对于拳套来说显然有点慢。

更好的方法实际上是 Fisher–Yates 洗牌算法，这是 1938 年 Ronald Fisher 和 Frank Yates 所提出的算法（参见Fisher-Yates shuffle），记录在他们撰写的书籍《Statistical tables for biological, agricultural and medical research》中。这个算法也被记录在 Donald Knuth 撰写的著名书籍《计算机程序设计艺术》（The Art of Computer Programming）中，其基本过程如下：

To shuffle an array a of n elements (indices 0..n-1):
for i from n - 1 downto 1 do
j = random integer with 0 <= j <= i
exchange a[j] and a[i]

可以证明，算法的复杂度可以降低到 O(n)。同时，这种方法可以达到等概率完美洗牌，即每一个生物出现在特定位置上的概率都是相等的。既然可以满足这样的要求，按照偶数编号杀戮自然也就满足了严格的公平性了。

---

什么？你说生物总数量是奇数，做不到严格“让宇宙里一半人口消失”？可能奇异博士看到的 1400 多万种方法中，唯一可以战胜的方法是让全宇宙生物总数量是奇数，然后让拳套出 Bug......