Bureau des Arts

L’algorithme de tirage au sort

Pour les plus curieux, voici l’algorithme utilisé pour le tirage au sort.

  1. Les spectacles sont d’abord ordonnés dans une liste S en fonction de leur ratio demande/offre, du plus demandé au moins demandé.
  2. La liste S est ensuite parcourue dans l’ordre, et pour chaque spectacle k donné, on crée une liste S.[k] :
  • On regroupe les gens selon la priorité p qu’ils ont accordée au spectacle dans une liste S.[k].[p] triée aléatoirement
  • Pour chaque groupe (liste S.[k].[p]), et pour chaque personne du groupe, on attribue les places jusqu’à ce qu’il n’y en ait plus, sachant que :
    • S’il faut une place double :
      • S’il reste encore deux places, on les attribue
      • S’il ne reste plus qu’une place et pas de désistement automatique, on attribue la place
      • Sinon, aucune place n’est attribuée. Tous les vœux suivants de la personne courante remontent alors de deux crans dans les priorités
    • S’il ne reste plus de places, tous les vœux suivants de la personne courante remontent d’un cran dans les priorités (deux rangs si c’était une double place).