Monsieur le président, avez-vous vraiment gagné cette élection ?

In [ ]:
%pylab inline
Populating the interactive namespace from numpy and matplotlib

La problématique

Cinq candidats s'affrontent lors d'une élection.

In [ ]:
candidats = ["Albert", "Marine", "Max", "Oscar", "Émilie"]

La liste bulletins ci-dessous donne les préférences des électeurs pour les candidats en lice. bulletins[k] est la liste des candidats dans l'ordre de préférence décroissante selon l'électeur k.

In [ ]:
bulletins = []
for _ in range(3273):
    bulletins.append(["Albert", "Marine", "Max", "Oscar", "Émilie"])
for _ in range(2182):
    bulletins.append(["Émilie", "Max", "Marine", "Oscar", "Albert"])
for _ in range(1818):
    bulletins.append(["Oscar", "Émilie", "Max", "Marine", "Albert"])
for _ in range(1636):
    bulletins.append(["Marine", "Oscar", "Max", "Émilie", "Albert"])
for _ in range(727):
    bulletins.append(["Max", "Émilie", "Marine", "Oscar", "Albert"])
for _ in range(364):
    bulletins.append(["Max", "Oscar", "Marine", "Émilie", "Albert"])
In [ ]:
bulletins[3270:3280]
Out[ ]:
[['Albert', 'Marine', 'Max', 'Oscar', 'Émilie'],
 ['Albert', 'Marine', 'Max', 'Oscar', 'Émilie'],
 ['Albert', 'Marine', 'Max', 'Oscar', 'Émilie'],
 ['Émilie', 'Max', 'Marine', 'Oscar', 'Albert'],
 ['Émilie', 'Max', 'Marine', 'Oscar', 'Albert'],
 ['Émilie', 'Max', 'Marine', 'Oscar', 'Albert'],
 ['Émilie', 'Max', 'Marine', 'Oscar', 'Albert'],
 ['Émilie', 'Max', 'Marine', 'Oscar', 'Albert'],
 ['Émilie', 'Max', 'Marine', 'Oscar', 'Albert'],
 ['Émilie', 'Max', 'Marine', 'Oscar', 'Albert']]

Le problème est d'élire le candidat qui convient le mieux aux électeurs. Le TP étudie plusieurs modes de scrutin.

L'idée de ce TP provient de la vidéo Monsieur le président, avez-vous vraiment gagné cette élection ?

Existe-t-il un mode de scrutin idéal ? Cette vidéo tente de répondre à cette question.

Définition d'un type Dico

Dans ce TP il serait utile de disposer d'une sorte de dictionnaire qui permette facilement d'associer une valeur int à une valeur str. Par exemple associer un nombre de votes à chaque candidat. On aimerait par exemple pouvoir écrire :

votes = Dico(candidats)
votes['Albert'] = 1
votes['Max'] = 4
print(votes)
  • La première ligne crée un dictionnaire à partir de la liste des noms des candidats. Les valeurs initialement associées aux noms sont initialement égales à 0.

  • Les secondes et troisièmes lignes modifient les valeurs associées aux noms 'Albert' et 'Max'.

  • La dernière ligne imprime l'état du dictionnaire.

La bonne nouvelle est qu'il est possible d'écrire en Python le code ci-dessus en créant un nouveau type.

Le code ci-dessous définit ce qu'est le type Dico :

In [ ]:
class Dico():
    def __init__(self, noms):
        n = len(noms)
        self.noms = noms
        self.valeurs = [0] * n
        
    def __setitem__(self, x, valeur):
        i = self.noms.index(x)
        self.valeurs[i] = valeur
        
    def __getitem__(self, x):
        i = self.noms.index(x)
        return self.valeurs[i]
    
    def __repr__(self):
        n = len(self.noms)
        L = [] 
        for i in range(n):
            L.append("%s : %d" % (self.noms[i], self.valeurs[i]))
        return '{' + ', '.join(L) + '}'   
    
    def __str__(self):
        return self.__repr__()

Nous laissons de côté pour le moment l'étude de ce code. Nous nous plaçons du côté du programmeur utilisateur de ce type qui peut maintenant écrire :

In [ ]:
votes = Dico(candidats)
votes
Out[ ]:
{Albert : 0, Marine : 0, Max : 0, Oscar : 0, Émilie : 0}
In [ ]:
votes['Albert'] = 1
votes['Max'] = 4
print(votes)
{Albert : 1, Marine : 0, Max : 4, Oscar : 0, Émilie : 0}

Une fonction de tri

Question 1

Dans la suite du TP il sera utile de pouvoir trier les candidats selon certains critères. Nous écrivons donc une fonction de tri.

Reprenez en l'adaptant le code de la fonction tri_insertion.

  • La fonction tri ne modifie pas la liste T. Elle crée une copie et elle retourne cette copie triée.
  • Dans la liste retournée, x1 est avant x2 si critere[x1] > critere[x2].
In [ ]:
def tri(T, critere):
    """ Retourne une copie de T triée selon l'ordre décroissant
        de critere.
    
        T est une liste de `str`.
        critere est un Dico construit à partir de T.
    """
    ### À COMPLÉTER

votes = Dico(candidats)
votes['Oscar'] = 4
votes['Max'] = 2
votes['Albert'] = 7
votes['Émilie'] = 1
tri(candidats, votes)

Cinq modes de scrutin

Question 2

Écrire la fonction classement.

L'électeur k vote pour le candidat qu'il a placé en tête dans la liste bulletins[k].

In [ ]:
def classement(candidats, bulletins):
    """ Retourne la liste des candidats triées dans l'ordre
        décroissant du nombre de votes obtenus.
    """
    ### À COMPLÉTER

classement(candidats, bulletins)

Question 3

Écrire la fonction elu_A.

In [ ]:
def elu_A(candidats, bulletins):
    """ Le candidat élu est celui qui a obtenu 
        le plus de suffrages.
    """
    ### À COMPLÉTER

elu_A(candidats, bulletins)

Question 4

Écrire la fonction selection.

In [ ]:
def selection(candidats, bulletins):
    """ Retourne une nouvelle liste bulletins en éliminant
        des classements les candidats qui ne sont pas
        dans la liste passée en argument.
    """
    ### À COMPLÉTER

selection(['Émilie', 'Oscar'], bulletins[3270:3280])

Question 5

Écrire la fonction elu_B.

In [ ]:
def elu_B(candidats, bulletins):
    """ Les deux candidats qui ont obtenu le plus de suffrages
        sont sélectionnés pour le second tour.     
        Celui des deux candidats à obtenir le plus de suffrages
        au second tour est élu.
    """
    ### À COMPLÉTER

elu_B(candidats, bulletins)

Question 6

Écrire la fonction elu_C.

In [ ]:
def elu_C(candidats, bulletins):
    """ À chaque tour, le candidat qui obtient le moins de
        suffrages est éliminé.
        Le dernier qui reste est le candidat élu.
    """
    ### À COMPLÉTER
        
elu_C(candidats, bulletins)

Question 7

Écrire la fonction elu_D.

In [ ]:
def elu_D(candidats, bulletins):
    """ Les électeurs classent les n candidats par ordre 
        de préférence.
        * Une place de premier donne n points
        * Une place de deuxième donne n - 1 points
        * ...
        * Une place de dernier donne 1 point
        Le candidat élu est celui à avoir obtenu le plus
        de point
    """
    ### À COMPLÉTER

elu_D(candidats, bulletins)

Question 8

Écrire la fonction elu_E.

In [ ]:
def elu_E(candidats, bulletins):
    """ Chaque candidat est confronté à tous les autres
        un par un. Le candidat élu est celui qui obtient
        le plus de victoires.
    """
    ### À COMPLÉTER

elu_E(candidats, bulletins)