选举中的算法问题

    

    

    

    大多数人的记忆中都会有上小学时选班长的情景，再后来，我们也经历过许多不同的选举过程。如何设计公平合理的选举规则是远远超出了数学和算法范畴的复杂问题。本文只讨论在特定规则下如何获得选举结果的相关的算法。

    一群人按照一人一票的方式（每张选票具有相同权重）在（通常数量很少的）候选人中选出一位“胜出者”（如班长），最简单的规则就是票数最多者当选（假设没有并列）。在没有电子手段之前，最流行的做法就是投票完成后，将候选人名字列在黑板上，随着“唱票”进程，在候选人名字后画“正”字。最后数出每人得票数，即可知谁是当选者。

    模拟“画正字”的计票方式

    如果候选人人数k不大，可以定义k个元素的数组candidates，其中candidates[i]是整数，表示候选人i的得票数，i=0，1，…，k-1。若投票人数为n（通常n>>k），长度为n的整数序列vote_sequence可以看作所有选票的集合（次序无意义），其中，不在上述i定义范围内的项为无效选票。图1所示是模拟计票的过程。

    得到计票值后，数组candidates中的最大值对应的候选人即“胜出者”，如果对candidates排序，则可以得到所有候选人得票数的递增或递减序列。在本专栏我们曾讨论过排序问题[1]（文章刊登于本刊2020年第7期），知道基于key比较的排序算法在最坏情况下最优解的复杂度下限为nlogn。但这里是对candidates（大小为k）排序，而不是对vote_sequence（大小是n）排序，因此可以说复杂度为O（klogk）。另一方面，鉴于在大多数表决类应用场景下，k值远小于n，甚至可以认为与n的大小没有关系，即可看作是常量，也可以从vote_sequence的角度来看这排序过程。也就是想象有若干一字排开的“桶”，数量相对于n很小，例如有一个与n无关的常数上界c。一次性顺序扫描vote_sequence，每个元素尝试依次与每个桶中的一个元素相比，发现相同就扔进去（其实就是计一次数），发现两次相继的比较为一大一小，就启用一个新桶插在中间，将元素扔进去。当然，两端的情况稍有点特殊。这样一来，扫描全部完成后就得到了最多c个依元素大小序排列的桶，依次输出桶中元素的个数，就得到了相当于是cadidates的排序。由于在一次性扫描vote_sequence过程中每个元素最多需要c次比较，与n无关，因此这里的排序代價也可以看作O（n）。

    基于“众数”的选举规则

    采用“简单多数”规则，当候选人数大于2时当选者未必能得到多数人的支持。为了避免这一缺憾，另一种常用的选举规则要求当选者得到的选票数必须大于投票者总数的一半（有些选举可能规定达到半数即可，本文后面的讨论要求当选者得票数必须大于半数）。

    不妨假设所有选票均为有效选票，选票上给出投票人选择的候选人序号（非负整数），所有选票可以表示为一个有限长度的输入序列。如果该序列中存在某个数值，出现次数大于序列长度的一半，则该数值称为序列中的“众数”。我们注意到，“众数”一词在统计学中不一定非得超过半数。这里借用此名词，在本文范围内一定是指出现次数大于总项数的一半。因此，如果众数存在，显然只有一个。

    我们可以将基于“众数”规则选举的计票过程抽象为：对于任意输入的有限长度序列，找出该序列中的众数，或者判定众数不存在。如果输入表示全部选票，则如果众数存在，问题的解即当选者，反之，若判定众数不存在，则确定“无当选者”。

    众数判定问题表述简单，也挺有趣。可能因为它较少出现在流行的算法教科书中，不时会被一些IT技术企业选择作为招聘面试题。面试者最容易想到的算法就是排序。一旦将输入序列排序，下面的两种方法均可得到需要的结果：

    （1）计数：扫描已排序的序列，可以依次统计出每个数值出现的次数。根据最大出现次数即可判定众数或者判定众数不存在。

    （2）中值：在已排序的序列中读出第n/2」项（n为序列长度）。对于按从小到大排序的序列，这是“中位数”。如果从该项起直到序列末尾的数值均相等，则该数值即为“众数”，否则序列中不存在众数。

    排序的代价是O（nlogn），对于这里的解题目标而言，似乎代价大了些。读者可能会看出，如果我们知道了中位数，不需要排序，只要扫描序列，统计中位数出现的次数就能得到需要的结果。因为序列中有众数当且仅当中位数即众数（为什么？）在大多数算法教科书中能找到计算中位数的线性代价算法，这里不再赘述。

    下面介绍一个非常巧妙的众数算法，不需要排序，而且比求中位数更简单。[2]

    如果长度为n的序列中确实存在众数c，其出现次数为t。如果从序列中删除两个不相等的元素，则剩下的序列中c仍然是众数。被删除的两项不相等，其中最多有一个是c，因此余下的序列长度为n-2，而包含的c至少为t-1个。根据众数定义t>n/2，则t-1>n/2-1=（n-2）/2。

    其实，对任一“候选值”，通过统计判定其是否众数很容易，代价是线性的。问题是如何找“候选值“，根据上述分析，删除不相等的两项，不会将可能存在的“候选者”漏掉，换句话说，当这一过程一直继续，到剩下的序列中只含一个值时（也可能不是一项），这个值即候选值。它未必是众数，但只要扫描一次原序列进行统计即可判定。

    算法包含两个部分，首先是希望筛选出候选值，然后是统计候选值出现次数是否大于序列总长度的一半。算法过程如上页图2所示。

    很显然，算法两个阶段代价均为O（n），因此总代价是线性的。这个算法在整个过程中完全不涉及未当选者得票数的相关数据，这对于算法的人性化而言（保护未当选者隐私）是很好的性质。

    要求投票人给出更多倾向性信息的选举

    上述选举规则非常简单，每张选票只需要给出投票人中意的一个候选人。但当候选人数大于2时，很难保证有众数存在，很常见的情况是得票数比较分散，要确保胜出者得票超过一半（甚至三分之二），有时需要多轮投票。

    如何使选举过程既能有效操作，同时也让选举结果更容易被接受，促进社会和谐，需要设计更复杂的选举过程。相关理论与分析已经成为数学在社会科学中应用的一个重要方面。[3]本文只通过一个例子讨论要求投票者提供更多意向信息的选举规则。

    某班级要推选出一人参加学校的演讲比赛，共有6名同学报名（用A、B、C、D、E、F表示）。全班同学需要投票选出一人代表班级参赛。为了避免选票过于分散，难以确定胜出者，可以考虑以下两种方案：

    （1）每张选票不是只填写一个候选人的名字，而是按照投票者意向强弱对6名候选人排序。

    （2）组织候选人进行一对一预选对抗赛，每位投票人（假设总数为奇数）对每组对抗者选定赞同者，按照多数原则决定二者之间的胜负，然后将所有预选赛的结果汇总，作为推举最终代表的基础数据。

    前者是实践中经常采用的方法，一般会将每位投票人给出的序号作为“得分”，累加后分值最小者当选。（当然也不能排除得分相等）

    后者似乎很少在实际选举中使用。但是读者很容易想到，体育比赛经常采用这样的方法（循环赛）确定冠军（“胜出者”）。原因是许多体育比赛项目一对一对抗结果往往有客观标准。其实第一种选举方案的选票包含了第二种方案能提供的信息（任何两个候选人，排序前者优于排序后者），但从第二种方案得到的信息确定胜出者仍然不是很容易的。下面，我们考虑如何从一对一对抗结果导出“名次”，包括第一名（“当选者”）。讨论采用体育循环赛的表示方式，在这个语境下介绍相关算法。当排名次问题解决了，决定选举胜出者的问题自然也解决了。

    假设6名候选人一对一对抗结果对每张选票采用简单多数汇总如图3所示，图中的有向边uv表示候选人u在一对一对抗中胜候选人v。

    这样的有向图称为“竞赛图”。如果不考虑边的方向，这是完全图，因此它能够完整准确地描述没有平局的“循环赛”的结果。从循环赛所有场次的胜负关系怎样才能合理地给出全部参赛者的名次呢？比较自然的想法是按照胜场多少排序。由图3可以得到表1。

    可以看到，胜出者是A。不过C可能会抱怨：虽然比A少了一个胜场，但击败的对手看上去比较强，而且还击败了排名第一的A。现实生活中很少有采用循环制的体育比赛结果没有人“吐槽”的。尽管不可能有让所有人都满意的方法，但如果能在简单地数胜出场次之上，多少也考虑对手强弱的因素，结果的可接受度应该会更好些。

    为了能体现胜出场次对手的强弱差异，可以定义得分向量sk=（Ak，Bk，Ck，Dk，Ek，Fk），其初始值（k=0）各分量值设定为1，sk+1各分量的值等于sk中该选手击败的各选手对应值之和。按照这一规则，计算前几个sk的值如下页表2所示（诸分量对应于A，B，C，D，E，F）。

    从表2中可看出，s4到s5各选手的排序没有变化。只要输入数据对应的有向图是强连通的，且选手人数不小于4，可以证明得分向量的值一定会收敛到一个固定次序，这就可作为排名。我们略去数学细节，只给出计算选手名次的算法，如果针对的是前面提到的选举问题，则排名第一的为当选者。

    首先给出所需数据的定义：

    player：选手名列表，输入，在整个算法过程中不改变。

    winning：每个选手战胜的对手列表，这是一个二维表，为了方便处理，即使无胜局的选手在列表中也有相应的项（空表）。上述例子中winning=[[B，D，E，F]，[D，E，F]，[A，B，D]，[E，F]，[C，F]，[C]]。winning相当于输入的竞赛图，在整个算法过程中不改变。

    score：得分向量，算法过程中更新，即上述的sk。注意：得分向量中每个分量对于选手的次序始终是列表player的次序，改变的只是分值。

    ranking：选手排名列表，在上述例子中初始值为[A，B，C，D，E，F]，score每轮更新后做一次排序。注意：每轮排序依据的关键字是score中的相应项，与ranking本身诸项值（选手名）无关。

    還需要定义下列函数：

    score_update：按照上文介绍的规则，更新得分向量的值。

    player_sort：根据得分向量各项值，对ranking中的选手名按照分值从大到小排序。此函数为布尔函数，如果本轮并未发生元素置换，返回false，否则返回true。在待排序对象很小时，效率不是问题，采用最简单的“冒泡”算法即可。

    player_number：此函数将选手名转换为该选手在列表player中的下标值。

    算法过程表述如上页图4所示。算法描述中按照本文例子的情况是6名选手，只要稍作修改便可以适用于不同的输入。

    参考文献：

    [1]陈道蓄.排序问题[J].中国信息技术教育，2020（07）：24-27.

    [2]Udi Manber.算法引论：一种创造性方法（中文版）[M].北京：电子工业出版社，2010.

    [3]Wallis，W.D..Mathematics of Elections and Voting[M]. Berlin：Springer， 2014.

    注：作者系南京大学软件学院原院长，计算机系原系主任。