Chi ha la maggioranza?

Quale algoritmo si può utilizzare per determinare chi, tra N candidati in una votazione, ha raggiunto la maggioranza assoluta?
Il metodo più semplice che possa venire in mente è quello di raggruppare le schede valide in mucchietti, uno per ogni candidato, per poi contare alla fine dello spoglio quante schede ci sono in ciascun mucchietto. Una semplice aritmetica e si scopre se uno dei candidati ha raggiunto la metà dei voti, più uno.
Esiste un metodo più semplice, che evita i conteggi, e lo si deve a due ricercatori, Robert S. Boyer e J. Strother Moore. Il loro Majority voting algorithm, pubblicato nel 1981, consente di determinare se uno dei candidati ha raggiunto la maggioranza assoluta, senza conoscere il numero di candidati, senza contare le singole schede ed effettuando due scorrimenti lineari delle schede.

L’algoritmo non ha reali applicazioni in campo elettorale, dove è proprio necessario per trasparenza il conteggio effettivo delle preferenze espresse. Ha invece applicazioni in informatica, quando è sufficiente determinare il nome del vincitore. In questi casi, infatti, prevale il vantaggio del tempo di esecuzione, che cresce linearmente con il numero dei voti da elaborare, e l’indipendenza dal numero dei candidati.

Vediamo come funziona l’algoritmo di Boyer-Moore, per trovare chi ha la maggioranza assoluta in una votazione.

Lo scenario della votazione

Supponiamo che si voti per scegliere tra N candidati, e che a priori non si conosca il numero dei candidati. Nel calcolo di chi ha la maggioranza assoluta, inoltre, si escludano le schede bianche o nulle.

L’algoritmo di Boyer-Moore è in grado di indicare il vincitore che abbia ricevuto la metà più uno delle preferenze, oppure se nessuno ha raggiunto la maggioranza assoluta.

I passi dell’algoritmo

Nella sua ricerca, l’algoritmo scorre due volte la sequenza di schede:

il primo passo dell’algoritmo è chiamato pairing o matching;
il secondo passo è chiamato counting o vote counting.

Durante il passo di pairing, l’algoritmo cerca di raggruppare gli elementi dell’array in coppie, verificando se gli elementi sono uguali o diversi.
Durante il passo di counting, l’algoritmo utilizza le informazioni raccolte nel passo di pairing per determinare l’elemento maggioritario, se esiste.

L’algoritmo di Majority voting di Boyer e Moore è un classico esempio di ragionamento creativo che semplifica un procedimento, ma richiede uno sforzo non banale per seguirne la logica. Avevo già incontrato una situazione simile, un po’ di mesi fa.

Passo di pairing

Nel primo passo, il pairing, si preparano 3 mucchietti (o pile), indipendentemente dal numero di candidati presenti (che peraltro non è noto a priori). Nel primo mucchietto si pongono le schede impilate una sull’altra, a faccia in su. Gli altri due mucchietti sono inizialmente vuoti. Chiamiamo i tre mucchietti rispettivamente A, B, C.

Fino a esaurimento del mucchietto A, si procede in questo modo:

se la pila B è vuota, la carta in cima ad A viene spostata in B;
se la pila B non è vuota, allora:
- se la carta in cima ad A indica un voto per lo stesso candidato della carta in cima a B, allora la carta viene spostata in B;
- in caso contrario la due carte vengono spostate sulla pila C.

Lo stato alla fine del pairing

Alla fine del pairing, il mucchietto A si sarà svuotato e il mucchietto C vedrà impilate delle carte a due a due diverse tra loro.
Il mucchietto B, invece, potrà essere vuoto oppure conterrà schede con preferenze per un solo candidato, chiamiamolo X.

Nel primo caso si potrà già rispondere alla domanda: «Chi ha la maggioranza assoluta?», «Nessuno!»
Infatti nessuno dei candidati potrà avere più di esattamente metà dei voti (che non bastano per vincere), cosa che si verifica solo se ciascuna coppia del mucchietto C ha una preferenza per uno stesso candidato. In tutti gli altri casi, anche chi avrà ottenuto più preferenze avrà meno della metà dei voti.

Nel secondo caso, vale lo stesso ragionamento per tutti i candidati, tranne che per X, che quindi è un potenziale vincitore. Serve un secondo passo, quello di counting.

Passo di counting

Nel secondo passo, fino a esaurimento della pila C, si procede in questo modo:

se la pila B è vuota, la carta in cima a C si sposta su B;
se la carta in cima a C riporta una preferenza per X:
- se la carta in cima a B riporta una preferenza per X, la carta si sposta su B;
- se invece indica una preferenza diversa da X, allora le carte in cima a B e a C si spostano in A;
se la carta in cima al mucchio C riporta una preferenza diversa da X:
- se la carta in cima a B riporta una preferenza diversa da X, la carta si sposta su B;
- se invece indica una preferenza per X, allora le carte in cima a B e a C si spostano in A.

Quando avremo svuotato C, allora:

se la carta in cima a B (e automaticamente anche quelle sottostanti) indica preferenza per X, allora X è chi ha la maggioranza assoluta;
se la carta in cima a B indica una preferenza diversa da X, oppure se B è vuoto, allora nessun candidato ha la precedenza assoluta.

La logica con cui funziona il counting

Nel passo di counting, nella pila A si raggruppano coppie di schede che recano: una la preferenza per X, l’altra la preferenza per uno degli altri candidati.

Quindi, se la pila B contiene preferenze per X, queste saranno l’eccesso di voti per X, rispetto agli altri candidati messi insieme.
Se invece la pila B ha in cima una scheda con preferenza per un candidato diverso da X, allora B contiene l’eccesso di voti rispetto a X di tutti gli altri candidati. Nessun candidato ha quindi raggiunto la maggioranza assoluta.

La creatività di Boyer e Moore

Qualche anno prima, nel 1977, i due avevano già creato un altro algoritmo, alla base di diversi procedimenti di ricerca di pattern in stringhe. Lo si trova quindi nella ricerca di sotto-stringhe, analisi crittografiche e, in tempi più recenti, nella ricerca di sequenze di DNA all’interno di grandi genomi.
Una descrizione dell’algoritmo scritta da Moore si trova sul sito della Utexas.edu, Sempre nel medesimo sito, si trova anche una descrizione, per la stessa mano, dell’algoritmo di majority voting.

Immagine di WOKANDAPIX da Pixabay.