最近需要给公司内部编写一个随机生成人员名单的小工具，在解决这个问题的过程中，我认识到这是一个概率相关的问题，即使在过去我曾经设计过类似转盘抽奖这样的应用程序，可我并不认为我真正搞清楚了这个问题，所以想在这篇文章中说说我对概率问题的相关思考。首先，我们来考虑这个问题的背景，我们需要定期在内部举行英语交流活动，可是大家的英语水差异悬殊，所以如果按照常规的思路来解决这个问题，即认为每个人被选中的概率是相等的话，实际上对英语不好的人是显得不公平的。其次，作为一个内部活动它需要的是营造一种氛围，让每个人参与到其中，所以它要求英语好的人有一个相对高的优先级，这样能够方便在活动开始前“破冰”，可是同时它需要让英语不好的人能够参与其中，所以这个问题该如何解决呢？这就是我们今天想要讨论的话题！

今天吃什么

虽然我的确是一个对穿衣吃饭没有太多追求的人，可是作为这尘世间芸芸众生里最为普通的一个人，我们每天不可避免地会遇到这个问题。如同哲学家会从“认识你自己”这样一个基本命题发散出无数哲学问题一样，“今天吃什么”在某种意义上可能是比哲学问题还要重要的问题，尤其是对一个喜欢美食的吃货来讲，“今天吃什么”可能是整个世界里优先级最高的事情。

好了，我们从这个问题出发想要说明什么呢？通常我们解决这个问题最简单粗暴的方式是，罗列出附近所有的餐馆然后从中随机选择一家，现在主流的地图类 APP 基本上都有这样的功能，在每个餐馆被选中的概率相同的情况下，这种方案是没有什么问题的。可是我们都知道，人类作为这个世界上最复杂的一种动物，怎么会甘心让这个问题如此的简单呢？因为我们在选择的时候存在一个优先级的问题，例如我今天想吃红烧肉而明天想吃水煮鱼，显然因为个体偏好的差异每个餐馆被选中的概率是不相同的，因此在这种情况下，经典的概率理论是无法满足我们的要求的，那么此时该如何解决这个问题呢？

考虑到个人偏好对餐馆是否被选中的影响比较明显，因此实际上不同的餐馆拥有不同的优先级，这里我们假定有 A、B、C 三家餐馆，以你的个人喜好作为优先级评价标准，其优先级分别为 2、3、5，则根据概率知识可知，P(A)=0.2、P(B)=0.3、P(C)=0.5。我们这里采用一种累加的思路来处理，令 P(A)=P(A)=0.2、P(B)=P(A)+P(B)=0.5、P(C)=P(B)+P(C)=1，此时我们将 P(A)、P(B)、P(C)三个概率值标注在数轴上，根据几何概型的相关理论，我们很容易地可以知道，0~0.2 范围内可以表示餐馆 A 被选中的概率、0.2~0.5 可以表示餐馆 B 被选中的概率，0.5~1 可以表示餐馆 C 被选中的概率，此时我们可以借助各种编程语言提供的随机数功能来生成 0~1 间的随机数，然后根据随机数落在哪个区间内来处理结果。

我认为这个方案是比较不错的一种思路，在数学里有一种思想称为归一化，我们这里是将概率值从离散状态变为连续状态，而计算机更擅长我们生成一定范围内的随机数，所以这个方案为我们解决这类问题找到了一个不错的契合点，联想到转盘游戏其实是将 0~1 范围内的数字转换为 0~360 度范围内的角度，这一切就显得更加有趣啦！

概率与累积概率

在解决了“今天吃什么？”这样一个终极命题后，下面我们来从理论上对这个问题进行解释。第一个问题，什么是概率呢？根据百科全书中的定义，概率是概率论中的一个基本概念，它是度量随机事件发生的可能性的一个量，通常使用 0~1 间的实数来表示一个随机事件发生的可能性的大小，当其值越接近 0 时表示该随机事件越不可能发生，当其值月接近 1 时表示该随机事件越有可能发生。经典的古典概型理论指出，如果一个实验满足同时下列两个条件，则这样的实验就是古典实验：

• 实验只且只有有限个基本结果
• 每个基本结果出现的可能性相同

此时，对古典实验中的事件 A，其概率定义为：P(A)=m/n，其中 m 为事件 A 包含的基本结果的数目，n 为该实验中所有可能出现的基本结果的数目，这种概率定义的方法称为概率的古典定义。人们在重复实验的基础上进一步提出，在一定条件下，重复做 n 次重复实验，虽然实验次数的增加，如果某个事件的频率逐渐稳定在某一个数值 p 附近，则认为数值 p 即为事件 A 在该条件下发生的概率。这是建立在统计基础上的概率定义。显然我们发现这里存在问题，即古典概型是建立在所有事件发生的可能性相同这样一个基本假设的基础上的，于此同时我们可以注意到，概率是客观的而频率则依赖经验。对于概率甚至数学，人们一度认为它们都是严格的科学，对这种观点，我想引用庞加莱的一段话：

概率仅仅是我们无知程度的度量，据定义，我们不晓得其定律的现象，都是偶然现象。

好了，下面我们来关注一个新的概念，即累积分布函数(CDF，Cumulative Distribution Function)，它能够完整描述一个实数随机变量 X 的概率分布，是概率密度函数(pdf，probability density function)的积分。其数学定义是 F(X)=P(X<=x)，表示随机变量小于或者等于某个数值的概率。为什么我们需要连续的随机变量呢？因为计算机产生的随机数通常都是指某个范围内的随机变量，而通常意义上的古典概型实际上是一种离散分布的数学模型，显然这两者间需要某种形式上的转换，所以我们需要累积分布函数，并且对连续函数而言，所有小于或者等于某个数值 x 的概率都可以认为，它等于数值 x 处的概率，因为我们能够保证累积分布函数严格递增，印象中诸如正态分布、均匀分布、泊松分布都是可以采用这种思路来处理的。好啦，更多理论层面的内容大家有兴趣的话可以自己去探索，这里我们想在这种理论的基础上设计一个基本的抽奖系统。

一个抽奖系统的设计

首先，我们必须指出计算机产生的随机数都是伪随机数，因此我们无法编写出 100%随机的程序，而且事实上这种“随机”程度对我们来讲应该是完全足够了，所以在排除了这个因素的影响以后，我们基本上不能再为我们的应用程序寻找任何的借口，在这里我认为重要的一点是，我们能够有一个在理论和实践上都相对可行的方案，我们这里选择以一个简单的抽奖系统的设计为例来探讨这个问题。

随机概率公平吗

抽奖系统最重要的是什么呢？是公平合理，那么怎样保证每次抽奖对所有用户来讲都是公平的呢？我认为首先要能够指定一个公平合理的规则，因为规则就如同人世间的法律正义、就如同璀璨夜空中的星辰宇宙一样，当它被确定下来以后就会一种永恒的真理。我们现在来考虑这样一个概率问题，假设我们有 A、B、C、D 四种不同的物品，它们各自被选中的概率分别为 10%、20%、30%和 40%，我们应该如何解决这个问题呢？通常可以想到的一种方案是，因为这四种物品被选中的概率之和为 100%，因此我们将 0~100 范围内的数划分为[1,11)、[11,31)、[31,61)、[61,101)，我们注意到这四个区间都是左闭右开的，因此每个区间的长度和概率完全对应，此时我们产生一个(0,101)间的随机数，然后根据随机数落在那个区间内来判断抽取物品的结果，这种方法称为随机概率，我们来看看它是如何实现的：

static void Main(string[] args)
{
   List<Prize> prizes = new List<Prize>()
   {
      new Prize("奖品A",0.1d,1,11),
      new Prize("奖品B",0.2d,11,31),
      new Prize("奖品C",0.3d,31,61),
      new Prize("奖品D",0.4d,61,101)
   };

   var seed = Guid.NewGuid().GetHashCode();
   Random random = new Random(seed);
   int rand = random.Next(1, 101);

   var prize = prizes.Where(p => rand >= p.RangeStart && rand < p.RangeEnd).FirstOrDefault();
   Console.WriteLine("随机选取的物品为:" + prize.ID);             
}

这段代码是非常简单的，可我想要问的一个问题是，我们这样的做法到底对不对呢。面对一个概率学的问题，如果要检验我们的算法是否正确，一个最简单的方式是判断其是否符合我们的预期，因为从概率的定义中我们已经可以了解到，概率是一种数学定义中的概念，我们可以通过大量重复试验的客观性来证明概率的确是存在的，并且我们可以合理地解释它为什么这样，可是这样到底对不对，我相信没有人能够给出确定的答案。现在我们来借助计算机通过大量的重复实验来证明我们的方法是否正确，根据频率和概率的关系，我们知道频率应该会在概率的某一个范围内上下波动，但是它整体上会越来越接近于概率。下面的表格给出了我在这个问题上的试验结果：

这里因为博主在尝试做 1 亿次重复试验时电脑运行时间非常漫长，就像在电影《模仿游戏》中艾伦.图灵制作的计算机器在破解德国加密设备“恩格尼玛”时，常常需要长达数月的运算周期一样，这种类比可能不是非常恰当，因为现代计算机的硬件水平是图灵所处的二战时期难以企及的，可是我们忽然发现一个非常沮丧的事实，我们在这里处理 1 亿次左右的循环，依然需要一段我们感觉上非常“漫长”的时间，而根据电影中的情节，图灵制作的计算机器需要完成 159 亿次的运算来尝试各种可能的组合，所以此时此刻我们是应该向这些推动人类进步的杰出人物诚恳地致敬，因为我们今天的一切都是来自这些人在当时看似疯狂的举动，或许人们曾将他们视为疯子而我更喜欢将其视为天才。

结果的确如我们所预期的那样，这里每组试验都是 3 次平行试验后的平均值，可以看到随着重复次数的增加，试验结果更加趋向我们理论上设计的概率值，因此这种情况下我们认为这个设计是合理的，即这个算法是公平的。可是这个世界让人头疼的一点是，我们每个人都理所当然地认为，只要是别人能得到而我们自己得不到地，就一定是有内幕、是不公平地，可是这个世界本来就是不公平的啊，谁掌握更多的社会资源、谁掌握绝对的话语权，“正义”的天平就会向谁倾斜，我们能做的无非是让自己变得更好，努力避免陷入某种被动的局面。

好了，言归正传，现在我们会发现一个问题，这种方案在奖品种类非常多的情况下，调整概率会是一件非常困难的事情，这就像工程师不喜欢产品经理和游戏策划，其真实原因并非是工程师无法实现特定需求，而是在整个建筑完成规划和设计以后，频繁的需求变更让一座伟大的建筑变成了临时的脚手架，你必须认识到这是工程师经过创作以后的某种产出，你可以不在乎这些无人问津的代码，可是我作为工程师我一定要比任何人都要在乎啊。

可是一个新的问题是，你永远无法为用户提供一种通用的解决方案，一个简单的抽奖在引入各种“自定义”规则以后，就注定不会再成为一个简单的抽奖，因为揣测一个人会说什么，对我这样一个不喜欢说话的人来说简直是种灾难，同样地，用户让计算机来做什么就应该明确地告诉计算机，而不是让工程师用各种各样的 if-else 来揣测用户想要做什么，我们常常说“优雅接口、肮脏实现”，在某种意义上就是指这种东西在永远浪费工程师的时间，用户愚蠢、用户懒惰，可是他们居然可以凌驾于工程师之上，这是对这个世界最大的恶意。好了，我们现在来动手解决新的问题，当用户需要在抽奖的时候对各种条件进行筛选同时还要考虑优先级和公平性这样一个问题吧！

让一切可复用

首先我们来考虑，如何设计一个可以复用的抽奖系统，在这个问题中我们关注两点，第一，这个抽奖系统可以支持不同类型的“奖品”；第二，这个抽奖系统可以支持不同类型的“抽取”方式。因为在这个问题中，按照某种优先级随机抽取人员或者物品其实应该是一类问题，而抽取我们都知道应该有可放回抽取和不可放回抽取两种，所以我们可以考虑通过泛型和接口来实现这样的需求。我们在这里定义一个 IRankable 接口，所有的“奖品”都要实现该接口，其定义如下：

interface IRankable
{
   int GetRank();
}

我们可以发现该接口中只有一个 GetRank()方法，这是因为我们这里的概率算法的基础是权重，所以我们只要为不同类型的“奖品”建立其相应的权重模型，就可以实现对不同类型奖品的支持。现在我们需要编写一个随机生成“奖品”的随机生成器，我们应该可以想到通过接口来约束泛型的思路，所以下面我们来实现一个随机生成器 RandomGenerator。

首先我们可以想到的一点是，因为这里的泛型类型 T 需要实现 IRankable 接口，因此我们可以通过 IRankable 接口中定义的 GetRank()方法来获取不同奖品的权重，在此基础上我们对奖品按照权重进行分组，则我们可以计算出每种权重在整个奖品权重中占到的百分比，我们以此作为每种权重奖品的概率，利用累积概率的思想可以非常容易地获得各种权重奖品对应的概率范围。其代码实现如下：

/// <summary>
/// 计算概率
/// </summary>
private void CalculateProbability(IEnumerable<T> source)
{
   this.m_groups = source.GroupBy(e => e.GetRank());

   //计算总权重
   var totalRank = 0;
   m_source.ToList().ForEach((item) => { totalRank += item.GetRank(); });

   //计算每个权重对应的概率
   m_probs = new Dictionary<int, double>();
   foreach (IGrouping<int, T> group in m_groups)
   {
      var p = (double)(group.Key * group.Count() / (double)totalRank);
      m_probs.Add(group.Key, p);
   }

   //计算每个权重对应的累积概率(递增）
   var totalProb = 0d;
   m_totalProbs = new Dictionary<int, double>();
   foreach (KeyValuePair<int, double> kv in m_probs)
   {
      totalProb += kv.Value;
      m_totalProbs.Add(kv.Key, totalProb);
   }
}

好了，现在我们就获得了不同权重物品所对应的累积概率，即其概率范围，因此我们可以利用随机生成[0,1)范围内的随机数，然后判断随机数所在哪个概率范围内，我们就可以知道要对哪个权重分组中的奖品进行抽取，而对每个权重分组来说，因为其权重都是一样的，所以这里抽取试验可以认为是符合随机概率的，我们只需要从该分组中随机选取一个奖品返回就可以啦。那么这里该如何查找概率范围内，我们这里选择经典的“二分查找”算法：

/// <summary>
/// 返回概率所在的区间索引
/// </summary>
private int GetProbablityRange(Dictionary<int, double> totalProbs, 
      int begin, int end, double value)
{
   if (begin >= end) return begin;

   int mid = (begin + end) / 2;
   if (totalProbs.ElementAt(mid).Value >= value)
      return GetProbablityRange(totalProbs, begin, mid, value);
   else
      return GetProbablityRange(totalProbs, mid + 1, end, value);
}

那么好了，现在我们该怎么从这些奖品中随机抽取一个奖品呢，我们这里提供了随机生成 1 个奖品和随机生成指定数目个奖品的方法重载，我们以前者为例来看看它的实现过程:

/// <summary>
/// 随机抽取一个奖品
/// </summary>
public T Generate()
{
   //初始化随机数
   var seed = Guid.NewGuid().GetHashCode();
   var random = new Random(seed);

   //生成0到1间的随机数
   double rand = random.NextDouble();

   T result = default(T);

   //计算随机数落在哪个区间内 
   int index = GetProbablityRange(m_totalProbs, 0, m_totalProbs.Count - 1, rand);

   switch (m_option)
   {
      case GenerateOption.CanReplace:
         result = GenerateCanReplace(index, random);
         break;
      case GenerateOption.NoReplace:
         result = GetnerateNoReplace(index, random);
         break;
   }

   return result;
}

在这里我设计了两种不同的抽取方式，即可放回抽取和不可放回抽取，两者的区别在于前者奖品池中奖品的数目保持不变，而后者奖品池中奖品的数目会发生变化，而更本质的区别在于前者奖品概率保持不变，而后者概率会发生变化。后者在每次抽取完以后需要将抽中的奖品从奖品池中取出，重新计算概率后方能进行下一轮抽取，所以这里我们直接给出这两两种抽取方法的代码实现，这里需要考虑的一个问题是，在抽取指定数目个“奖品”的时候我们通常不希望出现重复的元素，前者需要我们判断已抽取的奖品列表中是否存在指定元素，而后者因为抽取的奖品会被取出，所以不需要考虑这种情况的处理。

/// <summary>
/// 可放回抽取/// 
</summary>
private T GenerateCanReplace(int index, Random random)
{
   int rank = m_totalProbs.ElementAt(index).Key;
   var group = m_groups.Where(e => e.Key == rank).FirstOrDefault();
   if (group == null)
      group = m_groups.ElementAt(random.Next(0, m_groups.Count()));
   return group.ElementAt(random.Next(0, group.ToList().Count));
}

/// <summary>
/// 不可放回抽取
/// </summary>
/// <returns></returns>
private T GetnerateNoReplace(int index, Random random)
{
   int rank = m_totalProbs.ElementAt(index).Key;
   var group = m_groups.Where(e => e.Key == rank).FirstOrDefault();
   if (group == null)
      group = m_groups.ElementAt(random.Next(0, m_groups.Count()));

   T result = group.ElementAt(random.Next(0, group.ToList().Count));

   //从集合中移除当前抽取的元素
   var list = m_source.ToList();
   list.Remove(result);

   //更新集合、重新计算概率
   m_source = list;
   CalculateProbability(m_source);
   return result;
}

在此基础上实现指定数目的奖品就会变得非常简单啦，因为我们只需要重复调用这个方法就可以啦，那么现在我们该如何使用这个随机生成器呢？一起来看一段示例代码：

//模拟优先级和员工级别对随机数的影响
List<Contract> contracts = new List<Contract>();
contracts.Add(new Contract() { Name = "People0", Level = "Senior", Priority = 1 });
contracts.Add(new Contract() { Name = "People1", Level = "Senior", Priority = 1 });
contracts.Add(new Contract() { Name = "People2", Level = "SSE", Priority = 10 });
contracts.Add(new Contract() { Name = "People3", Level = "SSE", Priority = 1 });
contracts.Add(new Contract() { Name = "People4", Level = "SSE", Priority = 1 });
contracts.Add(new Contract() { Name = "People5", Level = "SE", Priority = 1 });
contracts.Add(new Contract() { Name = "People6", Level = "SE", Priority = 1 });
contracts.Add(new Contract() { Name = "People7", Level = "SE", Priority = 1 });
contracts.Add(new Contract() { Name = "People8", Level = "SE", Priority = 1 });
contracts.Add(new Contract() { Name = "People9", Level = "SE", Priority = 1 });
contracts.Add(new Contract() { Name = "People10", Level = "Senior", Priority = 1 });
contracts.Add(new Contract() { Name = "People11", Level = "Senior", Priority = 1 });
contracts.Add(new Contract() { Name = "People12", Level = "SSE", Priority = 1 });
contracts.Add(new Contract() { Name = "People13", Level = "SSE", Priority = 1 });
contracts.Add(new Contract() { Name = "People14", Level = "SSE", Priority = 1 });
contracts.Add(new Contract() { Name = "People15", Level = "SE", Priority = 1 });
contracts.Add(new Contract() { Name = "People16", Level = "SE", Priority = 1 });
contracts.Add(new Contract() { Name = "People17", Level = "SE", Priority = 1 });
contracts.Add(new Contract() { Name = "People18", Level = "SE", Priority = 1 });
contracts.Add(new Contract() { Name = "People19", Level = "SE", Priority = 1 });

RandomGenerator<Contract> generator = 
   new RandomGenerator<Contract>(contracts,GenerateOption.NoReplace);
var list = generator.Generate(10);
foreach (var contract in list)
{
   Console.WriteLine(contract.Name);}
}

在这里 Contract 实现了 IRankable 接口，每个 Contract 的权重由 Level 和 Priority 两个属性来计算，示例中我们一次从集合中随机抽取了 10 个 Contract，而我们的算法能够保证它们都是不重复的，这个程序可以满足各种各样的抽取规则，比如按照 Contract 的口语、职位等不同的维度进行概率模型的建立即可，只要它实现了 IRankable 接口就可以使用这篇文章中的方法来随机抽取，这其实是一个业余时间的小项目啦，可我还是想让自己认真地考虑下这个问题，所以我花时间写了这篇文章，我对它的期望并没有太高，我喜欢将这些想法写下来而已。

小结

或许有些时候我们对一个事情的态度，对事情最终的走向起不了决定性的作用，尤其是在我们没有掌握话语权的时候。可我在考虑这个方案的时候，是明显地意识到程序永远无法满足人类的脑洞的需要，所以当我们在做一件事情的时候，就应该有意识地让自己想到它可能会有扩展性上的需求，我认为这是我们在做项目开发过程中需要去关注的一个点，如何让你的代码具备扩展性和可维护性，虽然有时候你想得太多会造成过度设计，可是如果你在项目前期做出了一个糟糕的规划，到了后期遭遇项目需求变更的时候就会非常痛苦，可不幸的是我在最近同时遭遇了这两种情况，或许这就是我想要强迫自己写完这篇文章的原因吧，这篇文章足足花了我两周的时间，我的拖延症啊什么时候能好啊！