Code source de parcoursup.ordreappel.OrdreAppel

#!/usr/bin/env python3
# -*- coding: utf-8; mode: python -*-
""" OrdreAppel, pour https://github.com/Naereen/ParcourSup.py.

- Auteurs : Lilian Besson, Bastien Trotobas et al, (C) 2018.
- Adresse : https://github.com/Naereen/ParcourSup.py
- Licence : MIT License (http://lbesson.mit-license.org).
"""
__author__ = "Lilian Besson, Bastien Trotobas et al"
__version__ = "0.0.1"


# XXX Pour utiliser l'implémentation dans scipy.stats
# import numpy as np
# from scipy.stats import kendalltau


[docs]class OrdreAppel(list): """ Classe représentant un ordre d'appel. Juste une liste avec une méthode en plus."""
[docs] def coefficientDivergence(self) -> float: """ Calcule une mesure de la différence entre le classement original et l'ordre d'appel, c'est le nombre d'inversions ramené au nombre maximal d'inversions. Le nombre maximal d'inversions est obtenu si le classement est totalement inversé (cas hypothétique), auquel cas il y a autant d'inversions que de paires non-ordonnées de candidat-e c'est-à-dire ``n * (n - 1) / 2``. .. note:: C'est la distance de Kendall-tau. """ # Note : on peut aussi la calculer comme ca : # if comp is None: # comp = sorted(self) # res = 1 - kendalltau(self, comp).pvalue # if np.isnan(res): # res = 0 # return res # if len(self) <= 1: return 0.0 nbInversions = 0 for i, voe1 in enumerate(self): # for j, voe2 in enumerate(self): for voe2 in self[:i]: # if j < i and voe1 < voe2: # une inversion ! if voe1 < voe2: # une inversion ! nbInversions += 1 maxNbInversions = (len(self) * (len(self) - 1) / 2) return nbInversions / float(maxNbInversions)
[docs]def main(taille=10, nbEssaisAleatoires=100000): """ Trace un histogramme de la répartition de ce ``coefficientDivergence()`` pour des listes de taille ``taille``.""" from math import factorial from itertools import permutations import numpy as np import matplotlib.pyplot as plt try: from tqdm import tqdm except: def tqdm(iterable=None, **kwargs): return iterable # on calcule le nombre d'essai à faire si on veut être exhaustif taillePermutations = int(factorial(taille)) if taillePermutations >= 1e8: print(f"Il y a {taillePermutations} permutations à essayer, cela fait trop, on va en essayer {nbEssaisAleatoires} aléatoires plutôt.") taillePermutations = nbEssaisAleatoires def permutations(liste): for _ in range(taillePermutations): yield np.random.permutation(liste) else: print(f"Il y a {taillePermutations} permutations à essayer.") # on calcule un tableau stockant des coefficients de divergence resultats = np.zeros(taillePermutations) liste_non_triee = list(range(taille)) for i, perm in tqdm(enumerate(permutations(liste_non_triee)), total=taillePermutations): resultats[i] = OrdreAppel(perm).coefficientDivergence() # et ensuite on en affiche un histogramme fig = plt.figure() plt.hist(resultats, bins=10*taille) plt.title(f"Histogramme de coefficientDivergence pour les permutations de [1,...,{taille}] et {taillePermutations} essais") plt.grid() plt.show() return fig
if __name__ == '__main__': from sys import argv taille = int(argv[1]) if len(argv) > 1 else 10 nbEssaisAleatoires = int(argv[2]) if len(argv) > 2 else 10000 main(taille=taille, nbEssaisAleatoires=nbEssaisAleatoires)