Implémentation simplifiée des algorithmes de ParcourSup

On utilise Python 3 dans ce document. Je vous conseille de le lire interactivement, en cliquant sur ce bouton là :

https://mybinder.org/v2/gh/Naereen/ParcourSup.py/master?filepath=notebooks%2FParcourSup.py_version_simplifiee.ipynb

In [1]:
%load_ext watermark
%watermark -a "Lilian Besson" -v
Lilian Besson 

CPython 3.5.2
IPython 6.3.1

Algorithme 1 : Ordre d'appel

On va donner ici une implémentation simplifiée de la fonction du calcul d'ordre d'appel, avec plusieurs exemples.

Types de candidats

Un candidat ou une candidate peut être boursier-ère ou non, et résident-e ou non. On a besoin de 4 types de candidats, qu'on représente simplement par un entier.

In [2]:
# Les différents types de candidats
BoursierResident       = 1
BoursierNonResident    = 2
NonBoursierResident    = 3
NonBoursierNonResident = 4
In [3]:
# Liste des différents types
TypesCandidats = [
    BoursierResident,
    BoursierNonResident,
    NonBoursierResident,
    NonBoursierNonResident
]

On définie également une fonction pour pouvoir afficher le type d'un candidat.

In [4]:
def afficheTypeCandidat(typeCandidat):
    if typeCandidat == BoursierResident:
        return "BoursierResident"
    elif typeCandidat == BoursierNonResident: 
        return "BoursierNonResident"
    elif typeCandidat == NonBoursierResident: 
        return "NonBoursierResident"
    elif typeCandidat == NonBoursierNonResident: 
        return "NonBoursierNonResident"

Un vœu

Un vœu désigne la candidature d'un candidat à une formation donnée. Ici on représente un vœu comme la donnée du type de candidat et du rang que l'établissement lui a atribué. On pourrait utiliser un tuple ou une liste pour représenter un vœu, par exemple [BoursierResident, 1, "Harry Potter"] pour un boursier résident classé 1er et appelé Harry Potter, mais par lisibilité on préfère utiliser un dictionnaire qui contient ces informations :

POUR NOUS ne même pas parler de nom mais juste d'identifiant ?

In [38]:
exemple_voeu = {
    "type": BoursierResident,
    "rang": 1,
    "nom": "Harry Potter",
    "id": 1235
}

En fait, on n'utilisera jamais le nom des vœux, parce que la plateforme ParcourSup ne tient compte d'aucune information sur les vœux ou les candidat-s, à part leur identifiant unique et anonymisé.

On ajoute un nom dans les premiers exemples simplement pour être un peu plus visuel. Les seules chosent que l'algorithme de ParcourSup utilise à propos des vœux sont leur type et leur rang. Dans le code ci-dessous, ils seront lu comme ça : voeu["type"] et voeu["rang"].

In [6]:
print("VÅ“u de type", afficheTypeCandidat(exemple_voeu["type"]), "et de rang", exemple_voeu["rang"])
VÅ“u de type BoursierResident et de rang 1

Une liste de vœux

Ensuite, une liste de vœux est une liste de dictionnaires de cette forme. Prenons un exemple avec 8 vœux, qui reprend l'exemple "A1" donné dans le document de référence.

Note : les prénoms sont choisis pour être dans l'ordre alphabétique.

In [39]:
voeu_alice      = { "type": NonBoursierNonResident, "rang": 1, "nom": "Alice" ,     "id": 1911}
voeu_bob        = { "type": NonBoursierNonResident, "rang": 2, "nom": "Bob",        "id": 2211}
voeu_christophe = { "type": NonBoursierNonResident, "rang": 3, "nom": "Christophe", "id": 1061}
voeu_dora       = { "type": NonBoursierNonResident, "rang": 4, "nom": "Dora",       "id": 7843}
voeu_emilie     = { "type": NonBoursierNonResident, "rang": 5, "nom": "Emilie",     "id": 3388}
voeu_florian    = { "type": BoursierNonResident,    "rang": 6, "nom": "Florian",    "id": 4073}
voeu_guillaume  = { "type": BoursierNonResident,    "rang": 7, "nom": "Guillaume",  "id": 8020}
voeu_helene     = { "type": NonBoursierNonResident, "rang": 8, "nom": "Hélène",     "id": 4219}

On a juste à les mettre dans une liste ensuite (en Python, une liste commence par [, chaque valeur est séparée par , et termine par ]).

In [8]:
voeuxClasses = [
    voeu_alice, voeu_bob, voeu_christophe, voeu_dora,
    voeu_emilie, voeu_florian, voeu_guillaume, voeu_helene
    # le retour à la ligne n'est là que pour une meilleure visibilité
]

On aura besoin de savoir si un type de candidat est boursier ou non (respectivement, est résident ou non). On ecrit deux fonctions pour faire ce test qui renvoie True si le candidat est du type proposé et False si ce n'est pas le cas.

In [9]:
def estBoursier(voeu):
    return voeu["type"] == BoursierResident or voeu["type"] == BoursierNonResident
In [10]:
def estResident(voeu):
    return voeu["type"] == BoursierResident or voeu["type"] == NonBoursierResident
In [11]:
print("Le vœu exemple est-il boursier ?", estBoursier(exemple_voeu))
print("Le vœu exemple est-il résident ?", estResident(exemple_voeu))
Le vœu exemple est-il boursier ? True
Le vœu exemple est-il résident ? True

Contraintes

L'algorithme ParcoursSup permet aux établissements de fixer des quotas minimaux sur le nombre de boursiers-ères et de résidents-es admis. On a besoin de connaître ces deux contraintes, exprimées en pourcentage donné comme un entier entre $0$ et $100$.

  • Par exemple ici, on demandera à avoir au moins 20% de boursiers-ères, mais aucune contrainte sur le taux de résidents-e-s.
In [12]:
tauxMinBoursiersPourcents = 20
tauxMinResidentsPourcents = 0

Algorithme

On devrait avoir tout ce qu'il faut.

L'algorithme est présenté comme suit dans le document de référence :

Nous avons essayé de rendre le code suivant le plus clair possible mais il est nécessairement un peu long. Forcez vous à le lire jusqu'au bout !

La fonction suivante passe par plusieurs étapes.

Je trouve le terme voeuxClasses ambigue, voeuxFormation pour l'ensemble des voeux d'une formation serait plus clair. Ton avis ?

Données d'entrée :

  • voeuxClasses : la listes des voeux postulant à une formation.
  • tauxMinBoursiersPourcents : le pourcentage minimale de boursiers que l'établissement souhaite recruter.
  • tauxMinResidentsPourcents : le pourcentage minimale de résidents que l'établissement souhaite recruter.
  • afficheTout : variable qui choisie si le fonction affiche ou non les explications.

Grosses étapes :

  1. Tri de la liste voeuxClasses selon le rang affecté à chaque candidat-e.
  2. On sépare la liste en quatres liste d'attente ordonnées, une par type de candidat-e.
  3. On créé la liste ordreAppel qui servira appeler les candidats-es sur le site. Elle est construite en ajoutant un par un tous-tes les candidats-es qui ont demandé cette formation. Pour cela on répète les actions jusqu'à ce que tous-tes les candidats-rs soient traités.
    1. On vérifie si les quotas fixés sont respectés et on détermine le type de candidat-e a recruter en fonction.
    2. On place à la suite de la liste ordreAppel le-a meilleur-e candidat-e du type choisi et on le retire de sa liste d'attente.
In [69]:
def calculerOrdreAppel(
        voeuxClasses,
        tauxMinBoursiersPourcents,
        tauxMinResidentsPourcents,
        afficheTout=True
    ):
    
    # On définit la fonction d'affichage que si on demande d'afficher tout.
    if afficheTout == False:
        def affiche(*args): pass
    else:  affiche = print
    
    # 1. On tri la liste voeuxClasses par ordre de rang
    affiche("\n1. On trie les vœux par rang")
    affiche("  Avant le tri :", voeuxClasses)
    voeuxClasses.sort(key=lambda voeu: -voeu["rang"])
    affiche("  Après le tri :", voeuxClasses)    
    
    # 2. On crée des listes de vœux pour chaque types de candidats
    affiche("\n2. On crée des listes triées pour chaque types de candidats")
    filesAttente = {
        BoursierResident: [ ],  # liste vide associée à chaque type
        BoursierNonResident: [ ],  # liste vide associée à chaque type
        NonBoursierResident: [ ],  # liste vide associée à chaque type
        NonBoursierNonResident: [ ],  # liste vide associée à chaque type
    }

    # Chaque voeu classé est placé dans la liste correspondante,
    # en fonction du type du candidat.
    # Les quatre listes obtenues sont ordonnées par rang de classement,
    # comme l'est la liste voeuxClasses.
    nbBoursiersTotal = 0
    nbResidentsTotal = 0

    for voeu in voeuxClasses:
        # on ajoute le voeu à la fin de la file (FIFO) correspondante
        filesAttente[voeu["type"]].append(voeu)
        if estBoursier(voeu):
            nbBoursiersTotal += 1
        if estResident(voeu):
            nbResidentsTotal += 1
            
    # Affichage des listes d'attentes
    affiche("  Liste des boursiers résident :\n\t", filesAttente[1])
    affiche("  Liste des boursiers non résident :\n\t", filesAttente[2])
    affiche("  Liste des boursiers non résident :\n\t", filesAttente[3])
    affiche("  Liste des non boursiers non résident :\n\t", filesAttente[4])

    nbVoeuxClasses     = len(voeuxClasses)
    nbAppeles          = 0
    nbBoursiersAppeles = 0
    nbResidentsAppeles = 0

    # la boucle ajoute les candidats un par un à la liste suivante, dans l'ordre d'appel.
    # On commence par un ordre d'appel vide (liste vide).
    ordreAppel = [ ]

    affiche("\n3. Début de la boucle while, on remplit l'ordre d'appel pour respecter les critères")

    while len(ordreAppel) < nbVoeuxClasses:
        # on calcule lequel ou lesquels des critères boursiers et résidents
        # contraignent le choix du prochain candidat dans l'ordre d'appel

        contrainteTauxBoursier = (nbBoursiersAppeles < nbBoursiersTotal) and ((nbBoursiersAppeles * 100) < tauxMinBoursiersPourcents * (nbAppeles + 1))
        affiche("\tLes boursiers représentent : ", (nbBoursiersAppeles * 100), "% et on en veut ", tauxMinBoursiersPourcents * (nbAppeles + 1), "%")
        affiche("\tIl reste des boursiers à appeler : ", (nbBoursiersAppeles < nbBoursiersTotal))
        affiche("\t\t=> Du coup on va appeler un boursier : ", contrainteTauxBoursier)

        contrainteTauxResident = (nbResidentsAppeles < nbResidentsTotal) and ((nbResidentsAppeles * 100) < tauxMinResidentsPourcents * (nbAppeles + 1))
        affiche("\tLes résident représentent : ", (nbResidentsAppeles * 100), "% et on en veut ", tauxMinResidentsPourcents * (nbAppeles + 1), "%")
        affiche("\tIl reste des résidents à appeler : ", (nbResidentsAppeles < nbResidentsTotal))
        affiche("\t\t=> Du coup on va appeler un résident : ", contrainteTauxResident)

        # on fait la liste des voeux satisfaisant
        # les deux contraintes à la fois, ordonnée par rang de classement
        eligibles = [ ]
        for queue in filesAttente.values():
            if queue:
                voeu = queue[-1]  # le meilleur a été ajouté en dernier
                if ((estBoursier(voeu) or not contrainteTauxBoursier)
                    and (estResident(voeu) or not contrainteTauxResident)):
                    eligibles.append(voeu)
        affiche("  Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :\n", eligibles)

        # stocke le meilleur candidat à appeler tout en respectant
        # les deux contraintes si possible
        # ou à défaut seulement la contrainte sur le taux boursier
        meilleur = None

        if len(eligibles) > 0:
            # on prend le meilleur de cette liste
            meilleur = max(eligibles, key=lambda voeu: -voeu["rang"])
            affiche("  La liste des éligibles n'est pas vide, donc le-la meilleur-e est le-la meilleur-e de cette liste =", meilleur)
        else:
            # la liste peut être vide dans le cas où les deux contraintes
            # ne peuvent être satisfaites à la fois.
            # Dans ce cas nécessairement il y a une contrainte sur chacun des deux taux
            # (donc au moins un boursier non encore sélectionné)
            # et il ne reste plus de boursier résident,
            # donc il reste au moins un boursier non résident
            CandidatsBoursierNonResident = filesAttente[BoursierNonResident]
            meilleur = max(CandidatsBoursierNonResident, key=lambda voeu: -voeu["rang"])
            affiche("  La liste des éligibles est pas vide, donc le-la meilleur-e est le-la meilleur-e de la liste des boursier-e-s non résident-e-s =", meilleur)

        # suppression du candidat choisi de sa file d'attente
        saFileAttente = filesAttente[meilleur["type"]]
        affiche("  On vérifie si le-la meilleur", meilleur, "est aussi le-la meilleur-e de sa liste contenant", len(saFileAttente), "candidat-e-s du type", meilleur['type'])
        meilleur_de_sa_liste = saFileAttente.pop()

        # ajout du meilleur candidat à l'ordre d'appel
        ordreAppel.append(meilleur)
        nbAppeles += 1
        affiche("  On ajoute le meilleur", meilleur, "à l'ordre d'appel, c'est le-la", nbAppeles, "ème à être appelé-e.")

        if estBoursier(meilleur):
            nbBoursiersAppeles += 1
            affiche("    En plus, c'est le-la", nbBoursiersAppeles, "ème boursier-e à être appelé-e.")
        if estResident(meilleur):
            nbResidentsAppeles += 1
            affiche("    En plus, c'est le-la", nbResidentsAppeles, "ème résident-e à être appelé-e.")

    # fin de la boucle while
    affiche("\n3. On a terminé la boucle, on a rempli l'ordre d'appel.")
    return ordreAppel

Exemple (A1)

Avec les valeurs prisent ci-dessus comme exemple :

In [70]:
calculerOrdreAppel(
    voeuxClasses,
    tauxMinBoursiersPourcents,
    tauxMinResidentsPourcents
)
1. On trie les vœux par rang
  Avant le tri : [{'type': 4, 'rang': 8, 'nom': 'Hélène'}, {'type': 2, 'rang': 7, 'nom': 'Guillaume'}, {'type': 2, 'rang': 6, 'nom': 'Florian'}, {'type': 4, 'rang': 5, 'nom': 'Emilie'}, {'type': 4, 'rang': 4, 'nom': 'Dora'}, {'type': 4, 'rang': 3, 'nom': 'Christophe'}, {'type': 4, 'rang': 2, 'nom': 'Bob'}, {'type': 4, 'rang': 1, 'nom': 'Alice'}]
  Après le tri : [{'type': 4, 'rang': 8, 'nom': 'Hélène'}, {'type': 2, 'rang': 7, 'nom': 'Guillaume'}, {'type': 2, 'rang': 6, 'nom': 'Florian'}, {'type': 4, 'rang': 5, 'nom': 'Emilie'}, {'type': 4, 'rang': 4, 'nom': 'Dora'}, {'type': 4, 'rang': 3, 'nom': 'Christophe'}, {'type': 4, 'rang': 2, 'nom': 'Bob'}, {'type': 4, 'rang': 1, 'nom': 'Alice'}]

2. On crée des listes triées pour chaque types de candidats
  Liste des boursiers résident :
	 []
  Liste des boursiers non résident :
	 [{'type': 2, 'rang': 7, 'nom': 'Guillaume'}, {'type': 2, 'rang': 6, 'nom': 'Florian'}]
  Liste des boursiers non résident :
	 []
  Liste des non boursiers non résident :
	 [{'type': 4, 'rang': 8, 'nom': 'Hélène'}, {'type': 4, 'rang': 5, 'nom': 'Emilie'}, {'type': 4, 'rang': 4, 'nom': 'Dora'}, {'type': 4, 'rang': 3, 'nom': 'Christophe'}, {'type': 4, 'rang': 2, 'nom': 'Bob'}, {'type': 4, 'rang': 1, 'nom': 'Alice'}]

3. Début de la boucle while, on remplit l'ordre d'appel pour respecter les critères
	Les boursiers représentent :  0 % et on en veut  20 %
	Il reste des boursiers à appeler :  True
		=> Du coup on va appeler un boursier :  True
	Les résident représentent :  0 % et on en veut  0 %
	Il reste des résidents à appeler :  False
		=> Du coup on va appeler un résident :  False
  Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :
 [{'type': 2, 'rang': 6, 'nom': 'Florian'}]
  La liste des éligibles n'est pas vide, donc le-la meilleur-e est le-la meilleur-e de cette liste = {'type': 2, 'rang': 6, 'nom': 'Florian'}
  On vérifie si le-la meilleur {'type': 2, 'rang': 6, 'nom': 'Florian'} est aussi le-la meilleur-e de sa liste contenant 2 candidat-es du type 2
  On ajoute le meilleur {'type': 2, 'rang': 6, 'nom': 'Florian'} à l'ordre d'appel, c'est le-la 1 ème à être appelé-e.
    En plus, c'est le-la 1 ème boursier-e à être appelé-e.
	Les boursiers représentent :  100 % et on en veut  40 %
	Il reste des boursiers à appeler :  True
		=> Du coup on va appeler un boursier :  False
	Les résident représentent :  0 % et on en veut  0 %
	Il reste des résidents à appeler :  False
		=> Du coup on va appeler un résident :  False
  Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :
 [{'type': 2, 'rang': 7, 'nom': 'Guillaume'}, {'type': 4, 'rang': 1, 'nom': 'Alice'}]
  La liste des éligibles n'est pas vide, donc le-la meilleur-e est le-la meilleur-e de cette liste = {'type': 4, 'rang': 1, 'nom': 'Alice'}
  On vérifie si le-la meilleur {'type': 4, 'rang': 1, 'nom': 'Alice'} est aussi le-la meilleur-e de sa liste contenant 6 candidat-es du type 4
  On ajoute le meilleur {'type': 4, 'rang': 1, 'nom': 'Alice'} à l'ordre d'appel, c'est le-la 2 ème à être appelé-e.
	Les boursiers représentent :  100 % et on en veut  60 %
	Il reste des boursiers à appeler :  True
		=> Du coup on va appeler un boursier :  False
	Les résident représentent :  0 % et on en veut  0 %
	Il reste des résidents à appeler :  False
		=> Du coup on va appeler un résident :  False
  Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :
 [{'type': 2, 'rang': 7, 'nom': 'Guillaume'}, {'type': 4, 'rang': 2, 'nom': 'Bob'}]
  La liste des éligibles n'est pas vide, donc le-la meilleur-e est le-la meilleur-e de cette liste = {'type': 4, 'rang': 2, 'nom': 'Bob'}
  On vérifie si le-la meilleur {'type': 4, 'rang': 2, 'nom': 'Bob'} est aussi le-la meilleur-e de sa liste contenant 5 candidat-es du type 4
  On ajoute le meilleur {'type': 4, 'rang': 2, 'nom': 'Bob'} à l'ordre d'appel, c'est le-la 3 ème à être appelé-e.
	Les boursiers représentent :  100 % et on en veut  80 %
	Il reste des boursiers à appeler :  True
		=> Du coup on va appeler un boursier :  False
	Les résident représentent :  0 % et on en veut  0 %
	Il reste des résidents à appeler :  False
		=> Du coup on va appeler un résident :  False
  Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :
 [{'type': 2, 'rang': 7, 'nom': 'Guillaume'}, {'type': 4, 'rang': 3, 'nom': 'Christophe'}]
  La liste des éligibles n'est pas vide, donc le-la meilleur-e est le-la meilleur-e de cette liste = {'type': 4, 'rang': 3, 'nom': 'Christophe'}
  On vérifie si le-la meilleur {'type': 4, 'rang': 3, 'nom': 'Christophe'} est aussi le-la meilleur-e de sa liste contenant 4 candidat-es du type 4
  On ajoute le meilleur {'type': 4, 'rang': 3, 'nom': 'Christophe'} à l'ordre d'appel, c'est le-la 4 ème à être appelé-e.
	Les boursiers représentent :  100 % et on en veut  100 %
	Il reste des boursiers à appeler :  True
		=> Du coup on va appeler un boursier :  False
	Les résident représentent :  0 % et on en veut  0 %
	Il reste des résidents à appeler :  False
		=> Du coup on va appeler un résident :  False
  Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :
 [{'type': 2, 'rang': 7, 'nom': 'Guillaume'}, {'type': 4, 'rang': 4, 'nom': 'Dora'}]
  La liste des éligibles n'est pas vide, donc le-la meilleur-e est le-la meilleur-e de cette liste = {'type': 4, 'rang': 4, 'nom': 'Dora'}
  On vérifie si le-la meilleur {'type': 4, 'rang': 4, 'nom': 'Dora'} est aussi le-la meilleur-e de sa liste contenant 3 candidat-es du type 4
  On ajoute le meilleur {'type': 4, 'rang': 4, 'nom': 'Dora'} à l'ordre d'appel, c'est le-la 5 ème à être appelé-e.
	Les boursiers représentent :  100 % et on en veut  120 %
	Il reste des boursiers à appeler :  True
		=> Du coup on va appeler un boursier :  True
	Les résident représentent :  0 % et on en veut  0 %
	Il reste des résidents à appeler :  False
		=> Du coup on va appeler un résident :  False
  Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :
 [{'type': 2, 'rang': 7, 'nom': 'Guillaume'}]
  La liste des éligibles n'est pas vide, donc le-la meilleur-e est le-la meilleur-e de cette liste = {'type': 2, 'rang': 7, 'nom': 'Guillaume'}
  On vérifie si le-la meilleur {'type': 2, 'rang': 7, 'nom': 'Guillaume'} est aussi le-la meilleur-e de sa liste contenant 1 candidat-es du type 2
  On ajoute le meilleur {'type': 2, 'rang': 7, 'nom': 'Guillaume'} à l'ordre d'appel, c'est le-la 6 ème à être appelé-e.
    En plus, c'est le-la 2 ème boursier-e à être appelé-e.
	Les boursiers représentent :  200 % et on en veut  140 %
	Il reste des boursiers à appeler :  False
		=> Du coup on va appeler un boursier :  False
	Les résident représentent :  0 % et on en veut  0 %
	Il reste des résidents à appeler :  False
		=> Du coup on va appeler un résident :  False
  Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :
 [{'type': 4, 'rang': 5, 'nom': 'Emilie'}]
  La liste des éligibles n'est pas vide, donc le-la meilleur-e est le-la meilleur-e de cette liste = {'type': 4, 'rang': 5, 'nom': 'Emilie'}
  On vérifie si le-la meilleur {'type': 4, 'rang': 5, 'nom': 'Emilie'} est aussi le-la meilleur-e de sa liste contenant 2 candidat-es du type 4
  On ajoute le meilleur {'type': 4, 'rang': 5, 'nom': 'Emilie'} à l'ordre d'appel, c'est le-la 7 ème à être appelé-e.
	Les boursiers représentent :  200 % et on en veut  160 %
	Il reste des boursiers à appeler :  False
		=> Du coup on va appeler un boursier :  False
	Les résident représentent :  0 % et on en veut  0 %
	Il reste des résidents à appeler :  False
		=> Du coup on va appeler un résident :  False
  Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :
 [{'type': 4, 'rang': 8, 'nom': 'Hélène'}]
  La liste des éligibles n'est pas vide, donc le-la meilleur-e est le-la meilleur-e de cette liste = {'type': 4, 'rang': 8, 'nom': 'Hélène'}
  On vérifie si le-la meilleur {'type': 4, 'rang': 8, 'nom': 'Hélène'} est aussi le-la meilleur-e de sa liste contenant 1 candidat-es du type 4
  On ajoute le meilleur {'type': 4, 'rang': 8, 'nom': 'Hélène'} à l'ordre d'appel, c'est le-la 8 ème à être appelé-e.

3. On a terminé la boucle, on a rempli l'ordre d'appel.
Out[70]:
[{'type': 2, 'rang': 6, 'nom': 'Florian'},
 {'type': 4, 'rang': 1, 'nom': 'Alice'},
 {'type': 4, 'rang': 2, 'nom': 'Bob'},
 {'type': 4, 'rang': 3, 'nom': 'Christophe'},
 {'type': 4, 'rang': 4, 'nom': 'Dora'},
 {'type': 2, 'rang': 7, 'nom': 'Guillaume'},
 {'type': 4, 'rang': 5, 'nom': 'Emilie'},
 {'type': 4, 'rang': 8, 'nom': 'Hélène'}]
  • Sur cet exemple, on constate que la contrainte sur les boursiers a pu aider le candidat Florian, qui étais classé 6ème (le meilleur parmi les boursiers) à remonter devant certains candidats non boursiers.

  • La suite est logique, entre Alice, Bob, Christophe et Dora, puis on voit que Guillaume est aussi passé devant d'autres candidats avec la contrainte de 20% de boursiers (après les 5 premiers candidats, dont un boursier, il faut ajouter Guillaume pour continuer à satisfaire la contrainte de minimum 20% de boursiers).

Visualisation interactive

Les morceaux suivants sont hors programme, ne regardez pas le détail du code.

Ils vont permettre d'explorer interactivement l'influence des deux taux minimums (taux de boursiers-ères et résidents-entes) sur le résultat de l'ordre d'appel.

In [15]:
from IPython.display import display
from ipywidgets import interact

On définit la fonction que l'on souhaite explorer :

In [16]:
def fait_fonctionATester(
    voeuxClasses,
    tauxMinBoursiersPourcents=20,
    tauxMinResidentsPourcents=0
):
    def fonctionATester(
        tauxMinBoursiersPourcents=tauxMinBoursiersPourcents,
        tauxMinResidentsPourcents=tauxMinResidentsPourcents
    ):
        ordreAppel = calculerOrdreAppel(
            voeuxClasses,
            tauxMinBoursiersPourcents,
            tauxMinResidentsPourcents,
            afficheTout=False  # on cache la sortie
        )
        res = [voeu["rang"] for voeu in ordreAppel]
        return res

    return fonctionATester

Par exemple, si on demande $90%$ de boursiers, on voit que les candidats classés 6ème (Florian) et 7ème (Guillaume) sont mis en avant.

In [17]:
fait_fonctionATester(voeuxClasses)(90, 0)
Out[17]:
[6, 7, 1, 2, 3, 4, 5, 8]

Mais la visualisation interactive suivante permet de suivre l'influence des deux paramètres sur la liste des rangs finaux beaucoup plus facilement.

In [18]:
interact(
    fait_fonctionATester(voeuxClasses, tauxMinBoursiersPourcents=20, tauxMinResidentsPourcents=0),
    tauxMinBoursiersPourcents=(0, 100, 1),
    tauxMinResidentsPourcents=(0, 100, 1)
);

Ca ne marche pas sur ma machine, mais sur une installation neuve ou sur MyBinder, tout fonctionne bien…

Autres exemples (A2, A4)

Le document de référence propose deux autres exemples de petite taille, notés A2 et A4.

A2 : 2% de boursiers-ères

Comme dans le document de référence : C1 C2 C3 C4 C5 B6 C7 C8, où B6 est boursier, et tous sont non résidents. (Plus besoin des noms dans cet exemple là, on les enlève)

In [19]:
C1 = { "type": NonBoursierNonResident, "rang": 1 }
C2 = { "type": NonBoursierNonResident, "rang": 2 }
C3 = { "type": NonBoursierNonResident, "rang": 3 }
C4 = { "type": NonBoursierNonResident, "rang": 4 }
C5 = { "type": NonBoursierNonResident, "rang": 5 }
B6 = { "type": BoursierNonResident,    "rang": 6 }
C7 = { "type": NonBoursierNonResident, "rang": 7 }
C8 = { "type": NonBoursierNonResident, "rang": 8 }
In [20]:
voeuxClasses_A2 = [C1, C2, C3, C4, C5, B6, C7, C8]

On reproduit l'exemple du document de référence, avant de vous laisser explorer l'influence des deux taux.

In [21]:
fait_fonctionATester(voeuxClasses_A2)(2, 0)
Out[21]:
[6, 1, 2, 3, 4, 5, 7, 8]
In [22]:
interact(
    fait_fonctionATester(
        voeuxClasses_A2, tauxMinBoursiersPourcents=2, tauxMinResidentsPourcents=0
    ),
    tauxMinBoursiersPourcents=(0, 100, 1),
    tauxMinResidentsPourcents=(0, 100, 1)
);

On remarque que même un minimum de $2%$ de boursiers-ères suffit à faire remonter le candidat B6 en tête.

L'ordre des rangs est respecté seulement si on a aucune contrainte sur le taux de boursiers.

In [23]:
fait_fonctionATester(voeuxClasses_A2)(0, 0)
Out[23]:
[1, 2, 3, 4, 5, 6, 7, 8]

A4 : 10% de boursiers-ères

Comme dans le document de référence : C1 B2 B3 C4 C5 C6 C7 B8 C9 C10, où B2 B3 et B8 sont boursiers et tous sont non résidents.

In [24]:
C1  = { "type": NonBoursierNonResident, "rang": 1 }
B2  = { "type": BoursierNonResident,    "rang": 2 }
B3  = { "type": BoursierNonResident,    "rang": 3 }
C4  = { "type": NonBoursierNonResident, "rang": 4 }
C5  = { "type": NonBoursierNonResident, "rang": 5 }
C6  = { "type": NonBoursierNonResident, "rang": 6 }
C7  = { "type": NonBoursierNonResident, "rang": 7 }
B8  = { "type": BoursierNonResident,    "rang": 8 }
C9  = { "type": NonBoursierNonResident, "rang": 9 }
C10 = { "type": NonBoursierNonResident, "rang": 10 }
In [25]:
voeuxClasses_A4 = [C1, B2, B3, C4, C5, C6, C7, B8, C9, C10]

On reproduit l'exemple du document de référence, avant de vous laisser explorer l'influence des deux taux.

In [26]:
fait_fonctionATester(voeuxClasses_A4)(10, 0)
Out[26]:
[2, 1, 3, 4, 5, 6, 7, 8, 9, 10]
In [27]:
interact(
    fait_fonctionATester(
        voeuxClasses_A4, tauxMinBoursiersPourcents=10, tauxMinResidentsPourcents=0
    ),
    tauxMinBoursiersPourcents=(0, 100, 1),
    tauxMinResidentsPourcents=(0, 100, 1)
);

Visualisations colorées

On va utiliser ipythonblocks.

In [28]:
from ipythonblocks import BlockGrid
In [29]:
couleursTypeCandidat = {
    NonBoursierNonResident: (200, 200, 200),  # gris
    NonBoursierResident:    (0, 0, 200),      # bleu
    BoursierNonResident:    (200, 0, 0),      # rouge
    BoursierResident:       (200, 0, 200),    # violet
}
In [30]:
def voirListeVoeu(voeuxClasses):
    nbVoeux = len(voeuxClasses)
    grille = BlockGrid(nbVoeux, 1, fill=(200, 200, 200))
    for i, voeu in enumerate(voeuxClasses):
        typeCandidat = voeu["type"]
        couleur = couleursTypeCandidat[typeCandidat]
        grille[0, i].set_colors(*couleur)
    return grille
In [31]:
voeuxClasses_A4
Out[31]:
[{'rang': 10, 'type': 4},
 {'rang': 9, 'type': 4},
 {'rang': 8, 'type': 2},
 {'rang': 7, 'type': 4},
 {'rang': 6, 'type': 4},
 {'rang': 5, 'type': 4},
 {'rang': 4, 'type': 4},
 {'rang': 3, 'type': 2},
 {'rang': 2, 'type': 2},
 {'rang': 1, 'type': 4}]
In [32]:
voirListeVoeu(voeuxClasses_A2)
Out[32]:
In [33]:
voirListeVoeu(voeuxClasses_A4)
Out[33]:

Les candidats-ates boursiers-ères sont en rouges. On peut visualiser que le calcul de l'ordre d'appel va faire remonter un-e candidat-e boursier-ère :

In [34]:
voirListeVoeu(calculerOrdreAppel(voeuxClasses_A2, 20, 20, False))
Out[34]:
In [35]:
voirListeVoeu(calculerOrdreAppel(voeuxClasses_A4, 20, 20, False))
Out[35]:

Entrée aléatoire

Pour des exemples plus complets, on génère ici une liste de vœux de taille fixée, où chaque vœu sera aléatoirement boursier ou non, résident ou non. Cela va permettre de mieux comprendre l'algorithme sur des entrées de taille plus grande.

In [36]:
import random
import math
In [62]:
def fait_voeuxClasses_aleatoire(
    taille=100,
    tauxBoursiers=20,
    tauxResidents=20,
    random_seed=0,
):
    random.seed(random_seed)
    # on commence par avoir une liste triée de non boursier non résident
    voeuxClasses = [
        {'type': NonBoursierNonResident, 'rang': i}
        for i in range(1, taille + 1)
    ]
    # pour certains candidats aléatoires on les transforme en boursier et/ou en résident
    nbBoursiers = int(math.ceil(taille * tauxBoursiers / 100.0))
    for voeu in random.sample(voeuxClasses, nbBoursiers):
        voeu['type'] = BoursierNonResident
    nbResidents = int(math.ceil(taille * tauxResidents / 100.0))
    for voeu in random.sample(voeuxClasses, nbResidents):
        if estBoursier(voeu): voeu['type'] = BoursierResident
        else: voeu['type'] = NonBoursierResident
    # on la mélange enfin et on la renvoie
    random.shuffle(voeuxClasses)
    return voeuxClasses
In [63]:
voeuxClasses_exemple = fait_voeuxClasses_aleatoire(
    70,
    tauxBoursiers=20,  # ~14 boursiers
    tauxResidents=20   # ~14 résidents
)

On va avoir en moyenne 14 boursiers-ères et 14 résidents-entes, avec quelques intersections.

In [64]:
voirListeVoeu(voeuxClasses_exemple)
Out[64]:
In [65]:
voeuxClasses_exemple_sortie = calculerOrdreAppel(
    voeuxClasses_exemple,
    tauxMinBoursiersPourcents=100,
    tauxMinResidentsPourcents=100,
    afficheTout=False
)
In [66]:
voirListeVoeu(voeuxClasses_exemple_sortie)
Out[66]:

On visualise assez bien : avec une contrainte un peu folle qui impose de prendre 100% des boursiers-ères (en rouge ou violet) et 100% des résidents (en bleu ou violet), l'algorithme d'appel a d'abord pris les candidats de types BoursierResident (violet), puis BoursierNonResident (rouge) car le décret officiel demande de favoriser les boursiers, puis les NonBoursierResident (bleu) et enfin les autres.

Une visualisation interactive plus complète

On peut combiner la visualisation interactive et la visualisation avec des couleurs. On va d'abord avoir une

In [67]:
def fait_fonctionATester_couleurs(
    taille=70,
    tauxBoursiers=20,
    tauxResidents=20,
    random_seed=0,
    tauxMinBoursiersPourcents=10,
    tauxMinResidentsPourcents=0
):
    def fonctionATester(
        taille=taille,
        tauxBoursiers=tauxBoursiers,
        tauxResidents=tauxResidents,
        random_seed=random_seed,
        tauxMinBoursiersPourcents=tauxMinBoursiersPourcents,
        tauxMinResidentsPourcents=tauxMinResidentsPourcents
    ):
        voeuxClasses = fait_voeuxClasses_aleatoire(
            taille,
            tauxBoursiers=tauxBoursiers,
            tauxResidents=tauxResidents,
            random_seed=random_seed
        )
        print("Visualisation de l'algorithme de calcul de l'ordre d'appel.")
        print("1. Vœux non triés par rang :")
        display(voirListeVoeu(voeuxClasses))
        print("2. Vœux triés par rang, mais pas par l'algorithme :")
        voeuxClasses_tries = sorted(voeuxClasses, key=lambda voeu: -voeu["rang"])
        display(voirListeVoeu(voeuxClasses_tries))
        print("3. Vœux triés par l'algorithme :")
        ordreAppel = calculerOrdreAppel(
            voeuxClasses,
            tauxMinBoursiersPourcents,
            tauxMinResidentsPourcents,
            afficheTout=False  # on cache la sortie
        )
        display(voirListeVoeu(ordreAppel))

    return fonctionATester
In [68]:
interact(
    fait_fonctionATester_couleurs(
        taille=70,
        tauxBoursiers=20,
        tauxResidents=20,
        random_seed=0,
        tauxMinBoursiersPourcents=10,
        tauxMinResidentsPourcents=0
    ),
    taille=(1, 500, 1),
    tauxBoursiers=(0, 100, 1),
    tauxResidents=(0, 100, 1),
    random_seed=(0, 1000, 1),
    tauxMinBoursiersPourcents=(0, 100, 1),
    tauxMinResidentsPourcents=(0, 100, 1)
);

Focalisation sur un candidat

Jusqu'ici on a visualisé l'ordre d'appel de toute la liste. On va se focaliser sur un seul candidat pour voir l'influence du comportement de tous les paramètres sur son ordre d'appel final.

In [114]:
def voirListeVoeu_avecFocus(voeuxClasses, randDuFocus):
    grille = voirListeVoeu(voeuxClasses)
    for i, voeu in enumerate(voeuxClasses):
        if voeu['rang'] != randDuFocus:
            r, g, b = grille[0, i].rgb
            grille[0, i].rgb = (max(0, int(r*0.65)), max(0, int(g*0.65)), max(0, int(b*0.65)))
    return grille
In [115]:
def fait_fonctionATester_unSeulFocus(
    taille=70,
    tauxBoursiers=20,
    tauxResidents=20,
    random_seed=0,
    rangDuFocus=1,
    focusEstBoursier=False,
    focusEstResident=False,
    tauxMinBoursiersPourcents=10,
    tauxMinResidentsPourcents=0
):
    def fonctionATester(
        taille=taille,
        tauxBoursiers=tauxBoursiers,
        tauxResidents=tauxResidents,
        random_seed=random_seed,
        rangDuFocus=1,
        focusEstBoursier=False,
        focusEstResident=False,
        tauxMinBoursiersPourcents=tauxMinBoursiersPourcents,
        tauxMinResidentsPourcents=tauxMinResidentsPourcents
    ):
        voeuxClasses = fait_voeuxClasses_aleatoire(
            taille,
            tauxBoursiers=tauxBoursiers,
            tauxResidents=tauxResidents,
            random_seed=random_seed
        )
        for voeu in voeuxClasses:
            if voeu['rang'] == rangDuFocus:
                if focusEstBoursier and focusEstResident:
                    voeu['type'] = BoursierResident
                elif focusEstBoursier and not focusEstResident:
                    voeu['type'] = BoursierNonResident
                elif not focusEstBoursier and focusEstResident:
                    voeu['type'] = NonBoursierResident
                else:
                    voeu['type'] = NonBoursierNonResident
        print("Visualisation de l'algorithme de calcul de l'ordre d'appel.")
        print("1. Vœux non triés par rang :")
        display(voirListeVoeu_avecFocus(voeuxClasses, rangDuFocus))
        print("2. Vœux triés par rang, mais pas par l'algorithme :")
        voeuxClasses_tries = sorted(voeuxClasses, key=lambda voeu: voeu["rang"])
        display(voirListeVoeu_avecFocus(voeuxClasses_tries, rangDuFocus))
        print("3. Vœux triés par l'algorithme :")
        ordreAppel = calculerOrdreAppel(
            voeuxClasses,
            tauxMinBoursiersPourcents,
            tauxMinResidentsPourcents,
            afficheTout=False  # on cache la sortie
        )
        display(voirListeVoeu_avecFocus(ordreAppel, rangDuFocus))

    return fonctionATester
In [116]:
# https://ipywidgets.readthedocs.io/en/latest/examples/Using%20Interact.html#Arguments-that-are-dependent-on-each-other
import ipywidgets
taille_widget = ipywidgets.IntSlider(min=1, max=200, step=1, value=10)
rang_widget = ipywidgets.IntSlider(min=1, max=200, step=1, value=1)

def update_taille_max(*args):
    rang_widget.max = taille_widget.value
rang_widget.observe(update_taille_max, 'value')
In [117]:
interact(
    fait_fonctionATester_unSeulFocus(
        taille=70,
        tauxBoursiers=20,
        tauxResidents=20,
        random_seed=0,
        rangDuFocus=1,
        focusEstBoursier=False,
        focusEstResident=False,
        tauxMinBoursiersPourcents=10,
        tauxMinResidentsPourcents=0
    ),
    taille=taille_widget,
    tauxBoursiers=(0, 100, 1),
    tauxResidents=(0, 100, 1),
    random_seed=(0, 1000, 1),
    rangDuFocus=rang_widget,
    focusEstBoursier=False,
    focusEstResident=False,
    tauxMinBoursiersPourcents=(0, 100, 1),
    tauxMinResidentsPourcents=(0, 100, 1)
);

Algorithme 2 : Calcul des propositions

In [73]:
from IPython.display import HTML
In [74]:
HTML("<center><span style='color:red; font-size: xx-large;'>{}</span></center>".format('TODO '*54))
Out[74]:
TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO

Conclusion

Ce petit notebook n'est pas terminé, c'est un test en cours de rédaction.