大多數(shù)人的記憶中都會(huì)有上小學(xué)時(shí)選班長的情景，再后來，我們也經(jīng)歷過許多不同的選舉過程。如何設(shè)計(jì)公平合理的選舉規(guī)則是遠(yuǎn)遠(yuǎn)超出了數(shù)學(xué)和算法范疇的復(fù)雜問題。本文只討論在特定規(guī)則下如何獲得選舉結(jié)果的相關(guān)的算法。

一群人按照一人一票的方式（每張選票具有相同權(quán)重）在（通常數(shù)量很少的）候選人中選出一位“勝出者”（如班長），最簡單的規(guī)則就是票數(shù)最多者當(dāng)選（假設(shè)沒有并列）。在沒有電子手段之前，最流行的做法就是投票完成后，將候選人名字列在黑板上，隨著“唱票”進(jìn)程，在候選人名字后畫“正”字。最后數(shù)出每人得票數(shù)，即可知誰是當(dāng)選者。

模擬“畫正字”的計(jì)票方式

如果候選人人數(shù)k不大，可以定義k個(gè)元素的數(shù)組candidates，其中candidates[i]是整數(shù)，表示候選人i的得票數(shù)，i=0，1，…，k-1。若投票人數(shù)為n（通常n>>k），長度為n的整數(shù)序列vote_sequence可以看作所有選票的集合（次序無意義），其中，不在上述i定義范圍內(nèi)的項(xiàng)為無效選票。圖1所示是模擬計(jì)票的過程。

得到計(jì)票值后，數(shù)組candidates中的最大值對(duì)應(yīng)的候選人即“勝出者”，如果對(duì)candidates排序，則可以得到所有候選人得票數(shù)的遞增或遞減序列。在本專欄我們?cè)懻撨^排序問題[1]（文章刊登于本刊2020年第7期），知道基于key比較的排序算法在最壞情況下最優(yōu)解的復(fù)雜度下限為nlogn。但這里是對(duì)candidates（大小為k）排序，而不是對(duì)vote_sequence（大小是n）排序，因此可以說復(fù)雜度為O（klogk）。另一方面，鑒于在大多數(shù)表決類應(yīng)用場(chǎng)景下，k值遠(yuǎn)小于n，甚至可以認(rèn)為與n的大小沒有關(guān)系，即可看作是常量，也可以從vote_sequence的角度來看這排序過程。也就是想象有若干一字排開的“桶”，數(shù)量相對(duì)于n很小，例如有一個(gè)與n無關(guān)的常數(shù)上界c。一次性順序掃描vote_sequence，每個(gè)元素嘗試依次與每個(gè)桶中的一個(gè)元素相比，發(fā)現(xiàn)相同就扔進(jìn)去（其實(shí)就是計(jì)一次數(shù)），發(fā)現(xiàn)兩次相繼的比較為一大一小，就啟用一個(gè)新桶插在中間，將元素扔進(jìn)去。當(dāng)然，兩端的情況稍有點(diǎn)特殊。這樣一來，掃描全部完成后就得到了最多c個(gè)依元素大小序排列的桶，依次輸出桶中元素的個(gè)數(shù)，就得到了相當(dāng)于是cadidates的排序。由于在一次性掃描vote_sequence過程中每個(gè)元素最多需要c次比較，與n無關(guān)，因此這里的排序代價(jià)也可以看作O（n）。

基于“眾數(shù)”的選舉規(guī)則

采用“簡單多數(shù)”規(guī)則，當(dāng)候選人數(shù)大于2時(shí)當(dāng)選者未必能得到多數(shù)人的支持。為了避免這一缺憾，另一種常用的選舉規(guī)則要求當(dāng)選者得到的選票數(shù)必須大于投票者總數(shù)的一半（有些選舉可能規(guī)定達(dá)到半數(shù)即可，本文后面的討論要求當(dāng)選者得票數(shù)必須大于半數(shù)）。

不妨假設(shè)所有選票均為有效選票，選票上給出投票人選擇的候選人序號(hào)（非負(fù)整數(shù)），所有選票可以表示為一個(gè)有限長度的輸入序列。如果該序列中存在某個(gè)數(shù)值，出現(xiàn)次數(shù)大于序列長度的一半，則該數(shù)值稱為序列中的“眾數(shù)”。我們注意到，“眾數(shù)”一詞在統(tǒng)計(jì)學(xué)中不一定非得超過半數(shù)。這里借用此名詞，在本文范圍內(nèi)一定是指出現(xiàn)次數(shù)大于總項(xiàng)數(shù)的一半。因此，如果眾數(shù)存在，顯然只有一個(gè)。

我們可以將基于“眾數(shù)”規(guī)則選舉的計(jì)票過程抽象為：對(duì)于任意輸入的有限長度序列，找出該序列中的眾數(shù)，或者判定眾數(shù)不存在。如果輸入表示全部選票，則如果眾數(shù)存在，問題的解即當(dāng)選者，反之，若判定眾數(shù)不存在，則確定“無當(dāng)選者”。

眾數(shù)判定問題表述簡單，也挺有趣。可能因?yàn)樗^少出現(xiàn)在流行的算法教科書中，不時(shí)會(huì)被一些IT技術(shù)企業(yè)選擇作為招聘面試題。面試者最容易想到的算法就是排序。一旦將輸入序列排序，下面的兩種方法均可得到需要的結(jié)果：

（1）計(jì)數(shù)：掃描已排序的序列，可以依次統(tǒng)計(jì)出每個(gè)數(shù)值出現(xiàn)的次數(shù)。根據(jù)最大出現(xiàn)次數(shù)即可判定眾數(shù)或者判定眾數(shù)不存在。

（2）中值：在已排序的序列中讀出第n/2」項(xiàng)（n為序列長度）。對(duì)于按從小到大排序的序列，這是“中位數(shù)”。如果從該項(xiàng)起直到序列末尾的數(shù)值均相等，則該數(shù)值即為“眾數(shù)”，否則序列中不存在眾數(shù)。

排序的代價(jià)是O（nlogn），對(duì)于這里的解題目標(biāo)而言，似乎代價(jià)大了些。讀者可能會(huì)看出，如果我們知道了中位數(shù)，不需要排序，只要掃描序列，統(tǒng)計(jì)中位數(shù)出現(xiàn)的次數(shù)就能得到需要的結(jié)果。因?yàn)樾蛄兄杏斜姅?shù)當(dāng)且僅當(dāng)中位數(shù)即眾數(shù)（為什么？）在大多數(shù)算法教科書中能找到計(jì)算中位數(shù)的線性代價(jià)算法，這里不再贅述。

下面介紹一個(gè)非常巧妙的眾數(shù)算法，不需要排序，而且比求中位數(shù)更簡單。[2]

如果長度為n的序列中確實(shí)存在眾數(shù)c，其出現(xiàn)次數(shù)為t。如果從序列中刪除兩個(gè)不相等的元素，則剩下的序列中c仍然是眾數(shù)。被刪除的兩項(xiàng)不相等，其中最多有一個(gè)是c，因此余下的序列長度為n-2，而包含的c至少為t-1個(gè)。根據(jù)眾數(shù)定義t>n/2，則t-1>n/2-1=（n-2）/2。

其實(shí)，對(duì)任一“候選值”，通過統(tǒng)計(jì)判定其是否眾數(shù)很容易，代價(jià)是線性的。問題是如何找“候選值“，根據(jù)上述分析，刪除不相等的兩項(xiàng)，不會(huì)將可能存在的“候選者”漏掉，換句話說，當(dāng)這一過程一直繼續(xù)，到剩下的序列中只含一個(gè)值時(shí)（也可能不是一項(xiàng)），這個(gè)值即候選值。它未必是眾數(shù)，但只要掃描一次原序列進(jìn)行統(tǒng)計(jì)即可判定。

算法包含兩個(gè)部分，首先是希望篩選出候選值，然后是統(tǒng)計(jì)候選值出現(xiàn)次數(shù)是否大于序列總長度的一半。算法過程如上頁圖2所示。

很顯然，算法兩個(gè)階段代價(jià)均為O（n），因此總代價(jià)是線性的。這個(gè)算法在整個(gè)過程中完全不涉及未當(dāng)選者得票數(shù)的相關(guān)數(shù)據(jù)，這對(duì)于算法的人性化而言（保護(hù)未當(dāng)選者隱私）是很好的性質(zhì)。

要求投票人給出更多傾向性信息的選舉

上述選舉規(guī)則非常簡單，每張選票只需要給出投票人中意的一個(gè)候選人。但當(dāng)候選人數(shù)大于2時(shí)，很難保證有眾數(shù)存在，很常見的情況是得票數(shù)比較分散，要確保勝出者得票超過一半（甚至三分之二），有時(shí)需要多輪投票。

如何使選舉過程既能有效操作，同時(shí)也讓選舉結(jié)果更容易被接受，促進(jìn)社會(huì)和諧，需要設(shè)計(jì)更復(fù)雜的選舉過程。相關(guān)理論與分析已經(jīng)成為數(shù)學(xué)在社會(huì)科學(xué)中應(yīng)用的一個(gè)重要方面。[3]本文只通過一個(gè)例子討論要求投票者提供更多意向信息的選舉規(guī)則。

某班級(jí)要推選出一人參加學(xué)校的演講比賽，共有6名同學(xué)報(bào)名（用A、B、C、D、E、F表示）。全班同學(xué)需要投票選出一人代表班級(jí)參賽。為了避免選票過于分散，難以確定勝出者，可以考慮以下兩種方案：

（1）每張選票不是只填寫一個(gè)候選人的名字，而是按照投票者意向強(qiáng)弱對(duì)6名候選人排序。

（2）組織候選人進(jìn)行一對(duì)一預(yù)選對(duì)抗賽，每位投票人（假設(shè)總數(shù)為奇數(shù)）對(duì)每組對(duì)抗者選定贊同者，按照多數(shù)原則決定二者之間的勝負(fù)，然后將所有預(yù)選賽的結(jié)果匯總，作為推舉最終代表的基礎(chǔ)數(shù)據(jù)。

前者是實(shí)踐中經(jīng)常采用的方法，一般會(huì)將每位投票人給出的序號(hào)作為“得分”，累加后分值最小者當(dāng)選。（當(dāng)然也不能排除得分相等）

后者似乎很少在實(shí)際選舉中使用。但是讀者很容易想到，體育比賽經(jīng)常采用這樣的方法（循環(huán)賽）確定冠軍（“勝出者”）。原因是許多體育比賽項(xiàng)目一對(duì)一對(duì)抗結(jié)果往往有客觀標(biāo)準(zhǔn)。其實(shí)第一種選舉方案的選票包含了第二種方案能提供的信息（任何兩個(gè)候選人，排序前者優(yōu)于排序后者），但從第二種方案得到的信息確定勝出者仍然不是很容易的。下面，我們考慮如何從一對(duì)一對(duì)抗結(jié)果導(dǎo)出“名次”，包括第一名（“當(dāng)選者”）。討論采用體育循環(huán)賽的表示方式，在這個(gè)語境下介紹相關(guān)算法。當(dāng)排名次問題解決了，決定選舉勝出者的問題自然也解決了。

假設(shè)6名候選人一對(duì)一對(duì)抗結(jié)果對(duì)每張選票采用簡單多數(shù)匯總?cè)鐖D3所示，圖中的有向邊uv表示候選人u在一對(duì)一對(duì)抗中勝候選人v。

這樣的有向圖稱為“競(jìng)賽圖”。如果不考慮邊的方向，這是完全圖，因此它能夠完整準(zhǔn)確地描述沒有平局的“循環(huán)賽”的結(jié)果。從循環(huán)賽所有場(chǎng)次的勝負(fù)關(guān)系怎樣才能合理地給出全部參賽者的名次呢？比較自然的想法是按照勝場(chǎng)多少排序。由圖3可以得到表1。

可以看到，勝出者是A。不過C可能會(huì)抱怨：雖然比A少了一個(gè)勝場(chǎng)，但擊敗的對(duì)手看上去比較強(qiáng)，而且還擊敗了排名第一的A。現(xiàn)實(shí)生活中很少有采用循環(huán)制的體育比賽結(jié)果沒有人“吐槽”的。盡管不可能有讓所有人都滿意的方法，但如果能在簡單地?cái)?shù)勝出場(chǎng)次之上，多少也考慮對(duì)手強(qiáng)弱的因素，結(jié)果的可接受度應(yīng)該會(huì)更好些。

為了能體現(xiàn)勝出場(chǎng)次對(duì)手的強(qiáng)弱差異，可以定義得分向量sk=（Ak，Bk，Ck，Dk，Ek，F(xiàn)k），其初始值（k=0）各分量值設(shè)定為1，sk+1各分量的值等于sk中該選手擊敗的各選手對(duì)應(yīng)值之和。按照這一規(guī)則，計(jì)算前幾個(gè)sk的值如下頁表2所示（諸分量對(duì)應(yīng)于A，B，C，D，E，F(xiàn)）。

從表2中可看出，s4到s5各選手的排序沒有變化。只要輸入數(shù)據(jù)對(duì)應(yīng)的有向圖是強(qiáng)連通的，且選手人數(shù)不小于4，可以證明得分向量的值一定會(huì)收斂到一個(gè)固定次序，這就可作為排名。我們略去數(shù)學(xué)細(xì)節(jié)，只給出計(jì)算選手名次的算法，如果針對(duì)的是前面提到的選舉問題，則排名第一的為當(dāng)選者。

首先給出所需數(shù)據(jù)的定義：

player：選手名列表，輸入，在整個(gè)算法過程中不改變。

winning：每個(gè)選手戰(zhàn)勝的對(duì)手列表，這是一個(gè)二維表，為了方便處理，即使無勝局的選手在列表中也有相應(yīng)的項(xiàng)（空表）。上述例子中winning=[[B，D，E，F(xiàn)]，[D，E，F(xiàn)]，[A，B，D]，[E，F(xiàn)]，[C，F(xiàn)]，[C]]。winning相當(dāng)于輸入的競(jìng)賽圖，在整個(gè)算法過程中不改變。

score：得分向量，算法過程中更新，即上述的sk。注意：得分向量中每個(gè)分量對(duì)于選手的次序始終是列表player的次序，改變的只是分值。

ranking：選手排名列表，在上述例子中初始值為[A，B，C，D，E，F(xiàn)]，score每輪更新后做一次排序。注意：每輪排序依據(jù)的關(guān)鍵字是score中的相應(yīng)項(xiàng)，與ranking本身諸項(xiàng)值（選手名）無關(guān)。

還需要定義下列函數(shù)：

score_update：按照上文介紹的規(guī)則，更新得分向量的值。

player_sort：根據(jù)得分向量各項(xiàng)值，對(duì)ranking中的選手名按照分值從大到小排序。此函數(shù)為布爾函數(shù)，如果本輪并未發(fā)生元素置換，返回false，否則返回true。在待排序?qū)ο蠛苄r(shí)，效率不是問題，采用最簡單的“冒泡”算法即可。

player_number：此函數(shù)將選手名轉(zhuǎn)換為該選手在列表player中的下標(biāo)值。

算法過程表述如上頁圖4所示。算法描述中按照本文例子的情況是6名選手，只要稍作修改便可以適用于不同的輸入。

參考文獻(xiàn)：

[1]陳道蓄.排序問題[J].中國信息技術(shù)教育，2020（07）：24-27.

[2]Udi Manber.算法引論：一種創(chuàng)造性方法（中文版）[M].北京：電子工業(yè)出版社，2010.

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

注：作者系南京大學(xué)軟件學(xué)院原院長，計(jì)算機(jī)系原系主任。