{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Implémentation simplifiée des algorithmes de ParcourSup\n", "\n", "> - Pour plus de détails, voir [le projet sur GitHub](https://github.com/Naereen/ParcourSup.py/).\n", "> - Auteur(s) : [Lilian Besson](https://github.com/Naereen/) et [Bastien Trotobas](https://github.com/BastienTr).\n", "> - Date : Juillet 2018.\n", "> - Licence : [MIT](https://lbesson.mit-license.org/)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On utilise Python 3 dans ce document. Je vous conseille de le lire interactivement, en cliquant sur ce bouton là :\n", "\n", "https://mybinder.org/v2/gh/Naereen/ParcourSup.py/master?filepath=notebooks%2FParcourSup.py_version_simplifiee.ipynb" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Lilian Besson \n", "\n", "CPython 3.7.5\n", "IPython 7.8.0\n" ] } ], "source": [ "%load_ext watermark\n", "%watermark -a \"Lilian Besson\" -v" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithme 1 : Ordre d'appel\n", "\n", "On va donner ici une implémentation simplifiée de la fonction du calcul d'ordre d'appel, avec plusieurs exemples." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Types de candidats\n", "\n", "Un candidat ou une candidate peut être boursier-ère ou non, et résident-e ou non.\n", "On a besoin de 4 types de candidats, qu'on représente simplement par un entier." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "# Les différents types de candidats\n", "BoursierResident = 1\n", "BoursierNonResident = 2\n", "NonBoursierResident = 3\n", "NonBoursierNonResident = 4" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "# Liste des différents types\n", "TypesCandidats = [\n", " BoursierResident,\n", " BoursierNonResident,\n", " NonBoursierResident,\n", " NonBoursierNonResident\n", "]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On définie également une fonction pour pouvoir afficher le type d'un candidat." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "def afficheTypeCandidat(typeCandidat):\n", " if typeCandidat == BoursierResident:\n", " return \"BoursierResident\"\n", " elif typeCandidat == BoursierNonResident: \n", " return \"BoursierNonResident\"\n", " elif typeCandidat == NonBoursierResident: \n", " return \"NonBoursierResident\"\n", " elif typeCandidat == NonBoursierNonResident: \n", " return \"NonBoursierNonResident\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Un vœu\n", "\n", "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é.\n", "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 :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> *POUR NOUS* ne même pas parler de nom mais juste d'identifiant ?" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "exemple_voeu = {\n", " \"type\": BoursierResident,\n", " \"rang\": 1,\n", " \"nom\": \"Harry Potter\",\n", " \"id\": 1235\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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é*.\n", "\n", "On ajoute un nom dans les premiers exemples simplement pour être un peu plus visuel.\n", "Les seules chosent que l'algorithme de ParcourSup utilise à propos des vœux sont leur type et leur rang.\n", "Dans le code ci-dessous, ils seront lu comme ça : `voeu[\"type\"]` et `voeu[\"rang\"]`." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Vœu de type BoursierResident et de rang 1\n" ] } ], "source": [ "print(\"Vœu de type\", afficheTypeCandidat(exemple_voeu[\"type\"]), \"et de rang\", exemple_voeu[\"rang\"])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Une liste de vœux" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ensuite, une liste de vœux est une liste de dictionnaires de cette forme.\n", "Prenons un exemple avec 8 vœux, qui reprend l'exemple \"A1\" donné dans le document de référence.\n", "\n", "> Note : les prénoms sont choisis pour être dans l'ordre alphabétique." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "voeu_alice = { \"type\": NonBoursierNonResident, \"rang\": 1, \"nom\": \"Alice\" , \"id\": 1911}\n", "voeu_bob = { \"type\": NonBoursierNonResident, \"rang\": 2, \"nom\": \"Bob\", \"id\": 2211}\n", "voeu_christophe = { \"type\": NonBoursierNonResident, \"rang\": 3, \"nom\": \"Christophe\", \"id\": 1061}\n", "voeu_dora = { \"type\": NonBoursierNonResident, \"rang\": 4, \"nom\": \"Dora\", \"id\": 7843}\n", "voeu_emilie = { \"type\": NonBoursierNonResident, \"rang\": 5, \"nom\": \"Emilie\", \"id\": 3388}\n", "voeu_florian = { \"type\": BoursierNonResident, \"rang\": 6, \"nom\": \"Florian\", \"id\": 4073}\n", "voeu_guillaume = { \"type\": BoursierNonResident, \"rang\": 7, \"nom\": \"Guillaume\", \"id\": 8020}\n", "voeu_helene = { \"type\": NonBoursierNonResident, \"rang\": 8, \"nom\": \"Hélène\", \"id\": 4219}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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 `]`)." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "voeuxClasses = [\n", " voeu_alice, voeu_bob, voeu_christophe, voeu_dora,\n", " voeu_emilie, voeu_florian, voeu_guillaume, voeu_helene\n", " # le retour à la ligne n'est là que pour une meilleure visibilité\n", "]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "def estBoursier(voeu):\n", " return voeu[\"type\"] == BoursierResident or voeu[\"type\"] == BoursierNonResident" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "def estResident(voeu):\n", " return voeu[\"type\"] == BoursierResident or voeu[\"type\"] == NonBoursierResident" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Le vœu exemple est-il boursier ? True\n", "Le vœu exemple est-il résident ? True\n" ] } ], "source": [ "print(\"Le vœu exemple est-il boursier ?\", estBoursier(exemple_voeu))\n", "print(\"Le vœu exemple est-il résident ?\", estResident(exemple_voeu))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Contraintes\n", "\n", "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$.\n", "\n", "- Par exemple ici, on demandera à avoir au moins 20% de boursiers-ères, mais aucune contrainte sur le taux de résidents-e-s." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "tauxMinBoursiersPourcents = 20\n", "tauxMinResidentsPourcents = 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Algorithme\n", "\n", "On devrait avoir tout ce qu'il faut.\n", "\n", "L'algorithme est présenté comme suit dans [le document de référence](https://framagit.org/parcoursup/algorithmes-de-parcoursup/blob/master/doc/presentation_algorithmes_parcoursup.pdf) :\n", "\n", "\n", "\n", "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 !\n", "\n", "La fonction suivante passe par plusieurs étapes.\n", "\n", "> Je trouve le terme voeuxClasses ambigue, voeuxFormation pour l'ensemble des voeux d'une formation serait plus clair. Ton avis ?\n", "\n", "**Données d'entrée :** \n", "- voeuxClasses : la listes des voeux postulant à une formation.\n", "- tauxMinBoursiersPourcents : le pourcentage minimale de boursiers que l'établissement souhaite recruter.\n", "- tauxMinResidentsPourcents : le pourcentage minimale de résidents que l'établissement souhaite recruter.\n", "- afficheTout : variable qui choisie si le fonction affiche ou non les explications.\n", "\n", "**Grosses étapes :**\n", "1. Tri de la liste voeuxClasses selon le rang affecté à chaque candidat-e.\n", "1. On sépare la liste en quatres liste d'attente ordonnées, une par type de candidat-e.\n", "1. 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.\n", " 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.\n", " 1. 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." ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "code_folding": [] }, "outputs": [], "source": [ "def calculerOrdreAppel(\n", " voeuxClasses,\n", " tauxMinBoursiersPourcents,\n", " tauxMinResidentsPourcents,\n", " afficheTout=True\n", " ):\n", " \n", " # On définit la fonction d'affichage que si on demande d'afficher tout.\n", " if afficheTout == False:\n", " def affiche(*args): pass\n", " else: affiche = print\n", " \n", " # 1. On tri la liste voeuxClasses par ordre de rang\n", " affiche(\"\\n1. On trie les vœux par rang\")\n", " affiche(\" Avant le tri :\", voeuxClasses)\n", " voeuxClasses.sort(key=lambda voeu: -voeu[\"rang\"])\n", " affiche(\" Après le tri :\", voeuxClasses) \n", " \n", " # 2. On crée des listes de vœux pour chaque types de candidats\n", " affiche(\"\\n2. On crée des listes triées pour chaque types de candidats\")\n", " filesAttente = {\n", " BoursierResident: [ ], # liste vide associée à chaque type\n", " BoursierNonResident: [ ], # liste vide associée à chaque type\n", " NonBoursierResident: [ ], # liste vide associée à chaque type\n", " NonBoursierNonResident: [ ], # liste vide associée à chaque type\n", " }\n", "\n", " # Chaque voeu classé est placé dans la liste correspondante,\n", " # en fonction du type du candidat.\n", " # Les quatre listes obtenues sont ordonnées par rang de classement,\n", " # comme l'est la liste voeuxClasses.\n", " nbBoursiersTotal = 0\n", " nbResidentsTotal = 0\n", "\n", " for voeu in voeuxClasses:\n", " # on ajoute le voeu à la fin de la file (FIFO) correspondante\n", " filesAttente[voeu[\"type\"]].append(voeu)\n", " if estBoursier(voeu):\n", " nbBoursiersTotal += 1\n", " if estResident(voeu):\n", " nbResidentsTotal += 1\n", " \n", " # Affichage des listes d'attentes\n", " affiche(\" Liste des boursiers résident :\\n\\t\", filesAttente[1])\n", " affiche(\" Liste des boursiers non résident :\\n\\t\", filesAttente[2])\n", " affiche(\" Liste des boursiers non résident :\\n\\t\", filesAttente[3])\n", " affiche(\" Liste des non boursiers non résident :\\n\\t\", filesAttente[4])\n", "\n", " nbVoeuxClasses = len(voeuxClasses)\n", " nbAppeles = 0\n", " nbBoursiersAppeles = 0\n", " nbResidentsAppeles = 0\n", "\n", " # la boucle ajoute les candidats un par un à la liste suivante, dans l'ordre d'appel.\n", " # On commence par un ordre d'appel vide (liste vide).\n", " ordreAppel = [ ]\n", "\n", " affiche(\"\\n3. Début de la boucle while, on remplit l'ordre d'appel pour respecter les critères\")\n", "\n", " while len(ordreAppel) < nbVoeuxClasses:\n", " # on calcule lequel ou lesquels des critères boursiers et résidents\n", " # contraignent le choix du prochain candidat dans l'ordre d'appel\n", "\n", " contrainteTauxBoursier = (nbBoursiersAppeles < nbBoursiersTotal) and ((nbBoursiersAppeles * 100) < tauxMinBoursiersPourcents * (nbAppeles + 1))\n", " affiche(\"\\tLes boursiers représentent : \", (nbBoursiersAppeles * 100), \"% et on en veut \", tauxMinBoursiersPourcents * (nbAppeles + 1), \"%\")\n", " affiche(\"\\tIl reste des boursiers à appeler : \", (nbBoursiersAppeles < nbBoursiersTotal))\n", " affiche(\"\\t\\t=> Du coup on va appeler un boursier : \", contrainteTauxBoursier)\n", "\n", " contrainteTauxResident = (nbResidentsAppeles < nbResidentsTotal) and ((nbResidentsAppeles * 100) < tauxMinResidentsPourcents * (nbAppeles + 1))\n", " affiche(\"\\tLes résident représentent : \", (nbResidentsAppeles * 100), \"% et on en veut \", tauxMinResidentsPourcents * (nbAppeles + 1), \"%\")\n", " affiche(\"\\tIl reste des résidents à appeler : \", (nbResidentsAppeles < nbResidentsTotal))\n", " affiche(\"\\t\\t=> Du coup on va appeler un résident : \", contrainteTauxResident)\n", "\n", " # on fait la liste des voeux satisfaisant\n", " # les deux contraintes à la fois, ordonnée par rang de classement\n", " eligibles = [ ]\n", " for queue in filesAttente.values():\n", " if queue:\n", " voeu = queue[-1] # le meilleur a été ajouté en dernier\n", " if ((estBoursier(voeu) or not contrainteTauxBoursier)\n", " and (estResident(voeu) or not contrainteTauxResident)):\n", " eligibles.append(voeu)\n", " affiche(\" Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :\\n\", eligibles)\n", "\n", " # stocke le meilleur candidat à appeler tout en respectant\n", " # les deux contraintes si possible\n", " # ou à défaut seulement la contrainte sur le taux boursier\n", " meilleur = None\n", "\n", " if len(eligibles) > 0:\n", " # on prend le meilleur de cette liste\n", " meilleur = max(eligibles, key=lambda voeu: -voeu[\"rang\"])\n", " affiche(\" La liste des éligibles n'est pas vide, donc le-la meilleur-e est le-la meilleur-e de cette liste =\", meilleur)\n", " else:\n", " # la liste peut être vide dans le cas où les deux contraintes\n", " # ne peuvent être satisfaites à la fois.\n", " # Dans ce cas nécessairement il y a une contrainte sur chacun des deux taux\n", " # (donc au moins un boursier non encore sélectionné)\n", " # et il ne reste plus de boursier résident,\n", " # donc il reste au moins un boursier non résident\n", " CandidatsBoursierNonResident = filesAttente[BoursierNonResident]\n", " meilleur = max(CandidatsBoursierNonResident, key=lambda voeu: -voeu[\"rang\"])\n", " 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)\n", "\n", " # suppression du candidat choisi de sa file d'attente\n", " saFileAttente = filesAttente[meilleur[\"type\"]]\n", " 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'])\n", " meilleur_de_sa_liste = saFileAttente.pop()\n", "\n", " # ajout du meilleur candidat à l'ordre d'appel\n", " ordreAppel.append(meilleur)\n", " nbAppeles += 1\n", " affiche(\" On ajoute le meilleur\", meilleur, \"à l'ordre d'appel, c'est le-la\", nbAppeles, \"ème à être appelé-e.\")\n", "\n", " if estBoursier(meilleur):\n", " nbBoursiersAppeles += 1\n", " affiche(\" En plus, c'est le-la\", nbBoursiersAppeles, \"ème boursier-e à être appelé-e.\")\n", " if estResident(meilleur):\n", " nbResidentsAppeles += 1\n", " affiche(\" En plus, c'est le-la\", nbResidentsAppeles, \"ème résident-e à être appelé-e.\")\n", "\n", " # fin de la boucle while\n", " affiche(\"\\n3. On a terminé la boucle, on a rempli l'ordre d'appel.\")\n", " return ordreAppel" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exemple (A1)\n", "\n", "Avec les valeurs prisent ci-dessus comme exemple :" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "1. On trie les vœux par rang\n", " Avant le tri : [{'type': 4, 'rang': 1, 'nom': 'Alice', 'id': 1911}, {'type': 4, 'rang': 2, 'nom': 'Bob', 'id': 2211}, {'type': 4, 'rang': 3, 'nom': 'Christophe', 'id': 1061}, {'type': 4, 'rang': 4, 'nom': 'Dora', 'id': 7843}, {'type': 4, 'rang': 5, 'nom': 'Emilie', 'id': 3388}, {'type': 2, 'rang': 6, 'nom': 'Florian', 'id': 4073}, {'type': 2, 'rang': 7, 'nom': 'Guillaume', 'id': 8020}, {'type': 4, 'rang': 8, 'nom': 'Hélène', 'id': 4219}]\n", " Après le tri : [{'type': 4, 'rang': 8, 'nom': 'Hélène', 'id': 4219}, {'type': 2, 'rang': 7, 'nom': 'Guillaume', 'id': 8020}, {'type': 2, 'rang': 6, 'nom': 'Florian', 'id': 4073}, {'type': 4, 'rang': 5, 'nom': 'Emilie', 'id': 3388}, {'type': 4, 'rang': 4, 'nom': 'Dora', 'id': 7843}, {'type': 4, 'rang': 3, 'nom': 'Christophe', 'id': 1061}, {'type': 4, 'rang': 2, 'nom': 'Bob', 'id': 2211}, {'type': 4, 'rang': 1, 'nom': 'Alice', 'id': 1911}]\n", "\n", "2. On crée des listes triées pour chaque types de candidats\n", " Liste des boursiers résident :\n", "\t []\n", " Liste des boursiers non résident :\n", "\t [{'type': 2, 'rang': 7, 'nom': 'Guillaume', 'id': 8020}, {'type': 2, 'rang': 6, 'nom': 'Florian', 'id': 4073}]\n", " Liste des boursiers non résident :\n", "\t []\n", " Liste des non boursiers non résident :\n", "\t [{'type': 4, 'rang': 8, 'nom': 'Hélène', 'id': 4219}, {'type': 4, 'rang': 5, 'nom': 'Emilie', 'id': 3388}, {'type': 4, 'rang': 4, 'nom': 'Dora', 'id': 7843}, {'type': 4, 'rang': 3, 'nom': 'Christophe', 'id': 1061}, {'type': 4, 'rang': 2, 'nom': 'Bob', 'id': 2211}, {'type': 4, 'rang': 1, 'nom': 'Alice', 'id': 1911}]\n", "\n", "3. Début de la boucle while, on remplit l'ordre d'appel pour respecter les critères\n", "\tLes boursiers représentent : 0 % et on en veut 20 %\n", "\tIl reste des boursiers à appeler : True\n", "\t\t=> Du coup on va appeler un boursier : True\n", "\tLes résident représentent : 0 % et on en veut 0 %\n", "\tIl reste des résidents à appeler : False\n", "\t\t=> Du coup on va appeler un résident : False\n", " Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :\n", " [{'type': 2, 'rang': 6, 'nom': 'Florian', 'id': 4073}]\n", " 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', 'id': 4073}\n", " On vérifie si le-la meilleur {'type': 2, 'rang': 6, 'nom': 'Florian', 'id': 4073} est aussi le-la meilleur-e de sa liste contenant 2 candidat-e-s du type 2\n", " On ajoute le meilleur {'type': 2, 'rang': 6, 'nom': 'Florian', 'id': 4073} à l'ordre d'appel, c'est le-la 1 ème à être appelé-e.\n", " En plus, c'est le-la 1 ème boursier-e à être appelé-e.\n", "\tLes boursiers représentent : 100 % et on en veut 40 %\n", "\tIl reste des boursiers à appeler : True\n", "\t\t=> Du coup on va appeler un boursier : False\n", "\tLes résident représentent : 0 % et on en veut 0 %\n", "\tIl reste des résidents à appeler : False\n", "\t\t=> Du coup on va appeler un résident : False\n", " Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :\n", " [{'type': 2, 'rang': 7, 'nom': 'Guillaume', 'id': 8020}, {'type': 4, 'rang': 1, 'nom': 'Alice', 'id': 1911}]\n", " 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', 'id': 1911}\n", " On vérifie si le-la meilleur {'type': 4, 'rang': 1, 'nom': 'Alice', 'id': 1911} est aussi le-la meilleur-e de sa liste contenant 6 candidat-e-s du type 4\n", " On ajoute le meilleur {'type': 4, 'rang': 1, 'nom': 'Alice', 'id': 1911} à l'ordre d'appel, c'est le-la 2 ème à être appelé-e.\n", "\tLes boursiers représentent : 100 % et on en veut 60 %\n", "\tIl reste des boursiers à appeler : True\n", "\t\t=> Du coup on va appeler un boursier : False\n", "\tLes résident représentent : 0 % et on en veut 0 %\n", "\tIl reste des résidents à appeler : False\n", "\t\t=> Du coup on va appeler un résident : False\n", " Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :\n", " [{'type': 2, 'rang': 7, 'nom': 'Guillaume', 'id': 8020}, {'type': 4, 'rang': 2, 'nom': 'Bob', 'id': 2211}]\n", " 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', 'id': 2211}\n", " On vérifie si le-la meilleur {'type': 4, 'rang': 2, 'nom': 'Bob', 'id': 2211} est aussi le-la meilleur-e de sa liste contenant 5 candidat-e-s du type 4\n", " On ajoute le meilleur {'type': 4, 'rang': 2, 'nom': 'Bob', 'id': 2211} à l'ordre d'appel, c'est le-la 3 ème à être appelé-e.\n", "\tLes boursiers représentent : 100 % et on en veut 80 %\n", "\tIl reste des boursiers à appeler : True\n", "\t\t=> Du coup on va appeler un boursier : False\n", "\tLes résident représentent : 0 % et on en veut 0 %\n", "\tIl reste des résidents à appeler : False\n", "\t\t=> Du coup on va appeler un résident : False\n", " Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :\n", " [{'type': 2, 'rang': 7, 'nom': 'Guillaume', 'id': 8020}, {'type': 4, 'rang': 3, 'nom': 'Christophe', 'id': 1061}]\n", " 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', 'id': 1061}\n", " On vérifie si le-la meilleur {'type': 4, 'rang': 3, 'nom': 'Christophe', 'id': 1061} est aussi le-la meilleur-e de sa liste contenant 4 candidat-e-s du type 4\n", " On ajoute le meilleur {'type': 4, 'rang': 3, 'nom': 'Christophe', 'id': 1061} à l'ordre d'appel, c'est le-la 4 ème à être appelé-e.\n", "\tLes boursiers représentent : 100 % et on en veut 100 %\n", "\tIl reste des boursiers à appeler : True\n", "\t\t=> Du coup on va appeler un boursier : False\n", "\tLes résident représentent : 0 % et on en veut 0 %\n", "\tIl reste des résidents à appeler : False\n", "\t\t=> Du coup on va appeler un résident : False\n", " Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :\n", " [{'type': 2, 'rang': 7, 'nom': 'Guillaume', 'id': 8020}, {'type': 4, 'rang': 4, 'nom': 'Dora', 'id': 7843}]\n", " 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', 'id': 7843}\n", " On vérifie si le-la meilleur {'type': 4, 'rang': 4, 'nom': 'Dora', 'id': 7843} est aussi le-la meilleur-e de sa liste contenant 3 candidat-e-s du type 4\n", " On ajoute le meilleur {'type': 4, 'rang': 4, 'nom': 'Dora', 'id': 7843} à l'ordre d'appel, c'est le-la 5 ème à être appelé-e.\n", "\tLes boursiers représentent : 100 % et on en veut 120 %\n", "\tIl reste des boursiers à appeler : True\n", "\t\t=> Du coup on va appeler un boursier : True\n", "\tLes résident représentent : 0 % et on en veut 0 %\n", "\tIl reste des résidents à appeler : False\n", "\t\t=> Du coup on va appeler un résident : False\n", " Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :\n", " [{'type': 2, 'rang': 7, 'nom': 'Guillaume', 'id': 8020}]\n", " 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', 'id': 8020}\n", " On vérifie si le-la meilleur {'type': 2, 'rang': 7, 'nom': 'Guillaume', 'id': 8020} est aussi le-la meilleur-e de sa liste contenant 1 candidat-e-s du type 2\n", " On ajoute le meilleur {'type': 2, 'rang': 7, 'nom': 'Guillaume', 'id': 8020} à l'ordre d'appel, c'est le-la 6 ème à être appelé-e.\n", " En plus, c'est le-la 2 ème boursier-e à être appelé-e.\n", "\tLes boursiers représentent : 200 % et on en veut 140 %\n", "\tIl reste des boursiers à appeler : False\n", "\t\t=> Du coup on va appeler un boursier : False\n", "\tLes résident représentent : 0 % et on en veut 0 %\n", "\tIl reste des résidents à appeler : False\n", "\t\t=> Du coup on va appeler un résident : False\n", " Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :\n", " [{'type': 4, 'rang': 5, 'nom': 'Emilie', 'id': 3388}]\n", " 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', 'id': 3388}\n", " On vérifie si le-la meilleur {'type': 4, 'rang': 5, 'nom': 'Emilie', 'id': 3388} est aussi le-la meilleur-e de sa liste contenant 2 candidat-e-s du type 4\n", " On ajoute le meilleur {'type': 4, 'rang': 5, 'nom': 'Emilie', 'id': 3388} à l'ordre d'appel, c'est le-la 7 ème à être appelé-e.\n", "\tLes boursiers représentent : 200 % et on en veut 160 %\n", "\tIl reste des boursiers à appeler : False\n", "\t\t=> Du coup on va appeler un boursier : False\n", "\tLes résident représentent : 0 % et on en veut 0 %\n", "\tIl reste des résidents à appeler : False\n", "\t\t=> Du coup on va appeler un résident : False\n", " Les vœux satisfaisant les deux contraintes à la fois, ordonnés par rang de classement sont :\n", " [{'type': 4, 'rang': 8, 'nom': 'Hélène', 'id': 4219}]\n", " 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', 'id': 4219}\n", " On vérifie si le-la meilleur {'type': 4, 'rang': 8, 'nom': 'Hélène', 'id': 4219} est aussi le-la meilleur-e de sa liste contenant 1 candidat-e-s du type 4\n", " On ajoute le meilleur {'type': 4, 'rang': 8, 'nom': 'Hélène', 'id': 4219} à l'ordre d'appel, c'est le-la 8 ème à être appelé-e.\n", "\n", "3. On a terminé la boucle, on a rempli l'ordre d'appel.\n" ] }, { "data": { "text/plain": [ "[{'type': 2, 'rang': 6, 'nom': 'Florian', 'id': 4073},\n", " {'type': 4, 'rang': 1, 'nom': 'Alice', 'id': 1911},\n", " {'type': 4, 'rang': 2, 'nom': 'Bob', 'id': 2211},\n", " {'type': 4, 'rang': 3, 'nom': 'Christophe', 'id': 1061},\n", " {'type': 4, 'rang': 4, 'nom': 'Dora', 'id': 7843},\n", " {'type': 2, 'rang': 7, 'nom': 'Guillaume', 'id': 8020},\n", " {'type': 4, 'rang': 5, 'nom': 'Emilie', 'id': 3388},\n", " {'type': 4, 'rang': 8, 'nom': 'Hélène', 'id': 4219}]" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "calculerOrdreAppel(\n", " voeuxClasses,\n", " tauxMinBoursiersPourcents,\n", " tauxMinResidentsPourcents\n", ")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- 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.\n", "\n", "- 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)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Visualisation interactive\n", "\n", "Les morceaux suivants sont hors programme, *ne regardez pas le détail du code*.\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [], "source": [ "from IPython.display import display\n", "from ipywidgets import interact" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On définit la fonction que l'on souhaite explorer :" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "code_folding": [ 0, 4 ] }, "outputs": [], "source": [ "def fait_fonctionATester(\n", " voeuxClasses,\n", " tauxMinBoursiersPourcents=20,\n", " tauxMinResidentsPourcents=0\n", "):\n", " def fonctionATester(\n", " tauxMinBoursiersPourcents=tauxMinBoursiersPourcents,\n", " tauxMinResidentsPourcents=tauxMinResidentsPourcents\n", " ):\n", " ordreAppel = calculerOrdreAppel(\n", " voeuxClasses,\n", " tauxMinBoursiersPourcents,\n", " tauxMinResidentsPourcents,\n", " afficheTout=False # on cache la sortie\n", " )\n", " res = [voeu[\"rang\"] for voeu in ordreAppel]\n", " return res\n", "\n", " return fonctionATester" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "[6, 7, 1, 2, 3, 4, 5, 8]" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fait_fonctionATester(voeuxClasses)(90, 0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Mais la visualisation interactive suivante permet de suivre l'influence des deux paramètres sur la liste des rangs finaux beaucoup plus facilement." ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "b071698247574c2fb0e5976949fa4229", "version_major": 2, "version_minor": 0 }, "text/plain": [ "interactive(children=(IntSlider(value=20, description='tauxMinBoursiersPourcents'), IntSlider(value=0, descrip…" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "interact(\n", " fait_fonctionATester(voeuxClasses, tauxMinBoursiersPourcents=20, tauxMinResidentsPourcents=0),\n", " tauxMinBoursiersPourcents=(0, 100, 1),\n", " tauxMinResidentsPourcents=(0, 100, 1)\n", ");" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> Ca ne marche pas sur ma machine, mais sur une installation neuve ou sur [MyBinder](http://mybinder.org/), tout fonctionne bien…" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Autres exemples (A2, A4)\n", "\n", "Le document de référence propose deux autres exemples de petite taille, notés A2 et A4." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### A2 : 2% de boursiers-ères\n", "\n", "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.\n", "(Plus besoin des noms dans cet exemple là, on les enlève)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [], "source": [ "C1 = { \"type\": NonBoursierNonResident, \"rang\": 1 }\n", "C2 = { \"type\": NonBoursierNonResident, \"rang\": 2 }\n", "C3 = { \"type\": NonBoursierNonResident, \"rang\": 3 }\n", "C4 = { \"type\": NonBoursierNonResident, \"rang\": 4 }\n", "C5 = { \"type\": NonBoursierNonResident, \"rang\": 5 }\n", "B6 = { \"type\": BoursierNonResident, \"rang\": 6 }\n", "C7 = { \"type\": NonBoursierNonResident, \"rang\": 7 }\n", "C8 = { \"type\": NonBoursierNonResident, \"rang\": 8 }" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "voeuxClasses_A2 = [C1, C2, C3, C4, C5, B6, C7, C8]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On reproduit l'exemple du document de référence, avant de vous laisser explorer l'influence des deux taux." ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "[6, 1, 2, 3, 4, 5, 7, 8]" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fait_fonctionATester(voeuxClasses_A2)(2, 0)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "scrolled": true }, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "802a6b8a8da14b32b67ec31caeaa9c07", "version_major": 2, "version_minor": 0 }, "text/plain": [ "interactive(children=(IntSlider(value=2, description='tauxMinBoursiersPourcents'), IntSlider(value=0, descript…" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "interact(\n", " fait_fonctionATester(\n", " voeuxClasses_A2, tauxMinBoursiersPourcents=2, tauxMinResidentsPourcents=0\n", " ),\n", " tauxMinBoursiersPourcents=(0, 100, 1),\n", " tauxMinResidentsPourcents=(0, 100, 1)\n", ");" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On remarque que même un minimum de $2%$ de boursiers-ères suffit à faire remonter le candidat B6 en tête.\n", "\n", "L'ordre des rangs est respecté seulement si on a aucune contrainte sur le taux de boursiers." ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3, 4, 5, 6, 7, 8]" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fait_fonctionATester(voeuxClasses_A2)(0, 0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### A4 : 10% de boursiers-ères\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [], "source": [ "C1 = { \"type\": NonBoursierNonResident, \"rang\": 1 }\n", "B2 = { \"type\": BoursierNonResident, \"rang\": 2 }\n", "B3 = { \"type\": BoursierNonResident, \"rang\": 3 }\n", "C4 = { \"type\": NonBoursierNonResident, \"rang\": 4 }\n", "C5 = { \"type\": NonBoursierNonResident, \"rang\": 5 }\n", "C6 = { \"type\": NonBoursierNonResident, \"rang\": 6 }\n", "C7 = { \"type\": NonBoursierNonResident, \"rang\": 7 }\n", "B8 = { \"type\": BoursierNonResident, \"rang\": 8 }\n", "C9 = { \"type\": NonBoursierNonResident, \"rang\": 9 }\n", "C10 = { \"type\": NonBoursierNonResident, \"rang\": 10 }" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [], "source": [ "voeuxClasses_A4 = [C1, B2, B3, C4, C5, C6, C7, B8, C9, C10]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On reproduit l'exemple du document de référence, avant de vous laisser explorer l'influence des deux taux." ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "[2, 1, 3, 4, 5, 6, 7, 8, 9, 10]" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fait_fonctionATester(voeuxClasses_A4)(10, 0)" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "scrolled": true }, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "d9d3e9ed91554009b32ba8a2a4c9e9d7", "version_major": 2, "version_minor": 0 }, "text/plain": [ "interactive(children=(IntSlider(value=10, description='tauxMinBoursiersPourcents'), IntSlider(value=0, descrip…" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "interact(\n", " fait_fonctionATester(\n", " voeuxClasses_A4, tauxMinBoursiersPourcents=10, tauxMinResidentsPourcents=0\n", " ),\n", " tauxMinBoursiersPourcents=(0, 100, 1),\n", " tauxMinResidentsPourcents=(0, 100, 1)\n", ");" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Visualisations colorées\n", "On va utiliser [ipythonblocks](http://www.ipythonblocks.org/)." ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [], "source": [ "from ipythonblocks import BlockGrid" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [], "source": [ "couleursTypeCandidat = {\n", " NonBoursierNonResident: (200, 200, 200), # gris\n", " NonBoursierResident: (0, 0, 200), # bleu\n", " BoursierNonResident: (200, 0, 0), # rouge\n", " BoursierResident: (200, 0, 200), # violet\n", "}" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [], "source": [ "def voirListeVoeu(voeuxClasses):\n", " nbVoeux = len(voeuxClasses)\n", " grille = BlockGrid(nbVoeux, 1, fill=(200, 200, 200))\n", " for i, voeu in enumerate(voeuxClasses):\n", " typeCandidat = voeu[\"type\"]\n", " couleur = couleursTypeCandidat[typeCandidat]\n", " grille[0, i].set_colors(*couleur)\n", " return grille" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[{'type': 4, 'rang': 10},\n", " {'type': 4, 'rang': 9},\n", " {'type': 2, 'rang': 8},\n", " {'type': 4, 'rang': 7},\n", " {'type': 4, 'rang': 6},\n", " {'type': 4, 'rang': 5},\n", " {'type': 4, 'rang': 4},\n", " {'type': 2, 'rang': 3},\n", " {'type': 2, 'rang': 2},\n", " {'type': 4, 'rang': 1}]" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "voeuxClasses_A4" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/html": [ "