Scrutin jugement majoritaire

Discussion générale entre passionnés et amateurs de mathématiques sur des sujets mathématiques variés
emmesse
Membre Naturel
Messages: 14
Enregistré le: 08 Oct 2018, 08:48

scrutin jugement majoritaire

par emmesse » 07 Juin 2024, 19:18

Bonjour,

voici le scrutin à jugement majoritaire:

https://fr.wikipedia.org/wiki/Jugement_majoritaire

Comme l'explique Monsieur Balinski et Monsieur Laraki, le candidat élu est celui qui a le meilleur jugement majoritaire. Par contre, lorsque que plusieurs candidats on le même jugement majoritaire, on ne retient que ces candidats et on supprime la ligne des 50%, ainsi de suite jusqu'à ce que l'on ait qu'un candidat qui obtienne le jugement majoritaire, ou alors jusqu'à ce que il n'y ait plus qu'une ligne. dans ce dernier cas, si il y a plusieurs candidat ayant le meilleur jugement alors il y a ex æquo, sinon l'élu est celui qui a le meilleur jugement.
Tant qu'il y a ex æquo, on décrémente le nombre de votants des candidat pour leur jugement majoritaire et on décrémente le nombre de votants, puis on recalcule les jugements majoritaires. Je voudrais savoir si cela revient au même que l'algorithme récursif de M Balinski et M Laraki

Code: Tout sélectionner
//scrutin.hpp
#ifndef SCRUTIN_HPP
#define SCRUTIN_HPP

#include <map>
#include <vector>

#include "syntaxique.hpp"

class scrutin{
public:
  scrutin(std::string nomfichier);
  void elu();
private:
  syntaxique S;
  unsigned int nbvotants;
  std::map<std::string,int[6]> scores; //0:TB 1:B 2:AB 3:P 4:I 5:AR
  //scores est un map qui indique pour chaque candidats le nombre d'électeurs pour chaque jugement
  std::map<std::string,int>mentionchacun;
  //mentionchacun indique la mention majoritaire de chaque candidats
  std::vector<std::string>vec_nomscandidats;//liste des candidats
  std::vector<occurence_bulletin> vec_listebulletins;
  std::vector<std::string>nom_execo;//nom des candidats ayant obtenu ensemble la meilleure mention
  void garder_meilleure_mention();//supprimer
  void absentarejeter(occurence_bulletin &struct_bulletin);
  bool absent(occurence_bulletin const &struct_bulletin,std::string nom);
  void unjugementparcandidatetbulletin();
  void absentarejeter();
  void nomsvalides();
  void mentionmajoritaires();
  void calculscores();
  void afficherscores();
  bool execo();
  std::string mentionmini();
};
#endif

Code: Tout sélectionner
//scrutin.cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#include "scrutin.hpp"
#include "enumetstruct.hpp"

scrutin::scrutin(std::string nomfichier):S(nomfichier){
  S.anasynt(vec_nomscandidats,vec_listebulletins);//construit les candidats et les bulletins à partir du texte d'entrée
}

void scrutin::elu(){
  for(auto &struct_bulletin:vec_listebulletins){//pour chaque bulletin
    absentarejeter(struct_bulletin);//on attribue la mention "à rejeter" aux candidats absent du bulletin
  }
  nomsvalides();//vérifie que les noms sont constitués par un ensemble de mot débutant par une majuscule et éventuellement suivi de minuscules
  unjugementparcandidatetbulletin();//vérifie que, sur un bulletin de vote, un candidat n'a pas plus d'une mention
 
  if(vec_listebulletins.size()!=0){//si la liste des bulletins n'est pas vide
    calculscores();
    afficherscores();
    mentionmajoritaires();//calcule la mention majoritaire de chaque candidat
    garder_meilleure_mention();//supprime les candidate n'ayant pas la meilleure mention majoritaire
    while(nbvotants>1 && execo()){//La fonction execo retourne vrai si plus d'un candidat a le meilleure mention majoritaire
      for(auto nom:vec_nomscandidats)
   scores[nom][mentionchacun[nom]]--;//on décrémente la mention majoritaire dans les scores, pour chaque candidat
      nbvotants--;//le nombre de votant est alors décrémenté
      mentionmajoritaires();//calcule la nouvelle mention majoritaire de chaque candidat
      garder_meilleure_mention();//on supprime les candidats qui n'ont pas la meilleure mention majoritaire
    }
    if(execo()){
      std::cout<<"Ex æquo entre ";
      for(size_t i=0;i<nom_execo.size();i++){
   std::cout<<nom_execo[i];
   if(i+1<nom_execo.size())
     std::cout<<" et ";
      }
      std::cout<<std::endl;
    }
    else
      std::cout<<"Le candidat élu est "<<mentionmini()<<std::endl;
  }
  else
    std::cout<<"Pas de buletin valide"<<std::endl;
}

void scrutin::garder_meilleure_mention(){
  int mention_min=5;//à rejeter
  for(auto nom:vec_nomscandidats)
    if(mentionchacun[nom]<mention_min)
      mention_min=mentionchacun[nom];
  for(size_t i=0;i<vec_nomscandidats.size();i++){
    std::string nom=vec_nomscandidats[i];
    if(mentionchacun[nom]!=mention_min){
      vec_nomscandidats.erase(vec_nomscandidats.begin()+i);
      mentionchacun.erase(nom);
      scores.erase(nom);
      i=-1;
    }
  }
}

void scrutin::unjugementparcandidatetbulletin(){
  bool ecraser=false;
  for(size_t numbulletin=0;numbulletin<vec_listebulletins.size();numbulletin++){
    for(int jugement=0;jugement<6;jugement++)
      for(auto nom:vec_listebulletins[numbulletin].candidatmention[jugement])
   for(int compare=jugement+1;compare<6;compare++){
     std::vector<std::string>listenoms=vec_listebulletins[numbulletin].candidatmention[compare];
     if(find(listenoms.begin(),listenoms.end(),nom) != listenoms.end()){
       std::cerr<<"Présence d'un nom ayant plusieur mention dans le même bulletin. Bulletin nul"<<std::endl;
       ecraser=true;
     }
   }
    if(ecraser){
      vec_listebulletins.erase(vec_listebulletins.begin()+numbulletin);
      numbulletin--;
      ecraser=false;
    }
  }
}

void scrutin::mentionmajoritaires(){
  for(auto nomcandidat:vec_nomscandidats){
    long double mention=0.0;
    int jugement;
    for(jugement=0;jugement<6;jugement++){
      mention+=(long double)scores[nomcandidat][jugement]/(long double)nbvotants;
      if(mention>=0.5)
   break;
    }
    mentionchacun[nomcandidat]=jugement;
  }
}

bool scrutin::absent(occurence_bulletin const &struct_bulletin,std::string nom){
  for(int i=0;i<6;i++){
    std::vector<std::string>listenomsmention;
    listenomsmention=struct_bulletin.candidatmention[i];
    if(find(listenomsmention.begin(),listenomsmention.end(),nom) != listenomsmention.end())
      return false;
  }
  return true;
}

void scrutin::absentarejeter(occurence_bulletin &struct_bulletin){
  for(auto nom:vec_nomscandidats)
    if(absent(struct_bulletin,nom))
      struct_bulletin.candidatmention[5].push_back(nom);
}

void scrutin::nomsvalides(){
  for(size_t numbulletin=0;numbulletin<vec_listebulletins.size();numbulletin++){
    for(int jugement=0;jugement<6;jugement++){
      std::vector<std::string>listenoms;
      listenoms=vec_listebulletins[numbulletin].candidatmention[jugement];
      for(auto nom:listenoms)
   if(find(vec_nomscandidats.begin(),vec_nomscandidats.end(),nom)==vec_nomscandidats.end()){
     std::cerr<<"\""<<nom<<"\""<<" absent de la liste des candidats. Bulletin nul"<<std::endl;
     vec_listebulletins.erase(vec_listebulletins.begin()+numbulletin);
     if(numbulletin!=0){
       numbulletin--;
     }
   }
    }
  }
}

void scrutin::calculscores(){
  for(auto struct_bulletin:vec_listebulletins){
    for(int jugement=0;jugement<6;jugement++)
      for(auto nomcandidat:struct_bulletin.candidatmention[jugement])
   scores[nomcandidat][jugement]++;
  }
}

void scrutin::afficherscores(){
  unsigned int nbvotantsdansafficher=vec_listebulletins.size();
  for(auto nom:vec_nomscandidats){
    std::cout<<nom<<":"<<std::endl;
    for(int i=0;i<6;i++){
      switch(i){
      case 0:
   std::cout<<"très bien: "<<(long double)scores[nom][i]/(long double)nbvotantsdansafficher*100<<"%";
   break;
      case 1:
   std::cout<<"bien: "<<(long double)scores[nom][i]/(long double)nbvotantsdansafficher*100<<"%";
   break;
      case 2:
   std::cout<<"assez bien: "<<(long double)scores[nom][i]/(long double)nbvotantsdansafficher*100<<"%";
   break;
      case 3:
   std::cout<<"passable: "<<(long double)scores[nom][i]/(long double)nbvotantsdansafficher*100<<"%";
   break;
      case 4:
   std::cout<<"insuffisant: "<<(long double)scores[nom][i]/(long double)nbvotantsdansafficher*100<<"%";
   break;
      case 5:
   std::cout<<"à rejeter: "<<(long double)scores[nom][i]/(long double)nbvotantsdansafficher*100<<"%";
   break;
      }
      std::cout<<std::endl;
    }
    std::cout<<std::endl;
  }
}
   

bool scrutin::execo(){
  nom_execo.clear();
  int minimum=5;//5=à rejeter
  for(auto nom:vec_nomscandidats)
    if(mentionchacun[nom]<minimum)//si le candidat(nom) a une meilleure mention majoritaire
      minimum=mentionchacun[nom];//alors cette mention est retenue
  int compteur=0;
  for(auto nom:vec_nomscandidats){
    if(mentionchacun[nom]==minimum){
      compteur++;//compte combien de candidats ont la meileure mention majoritaire
      if(std::find(nom_execo.begin(),nom_execo.end(),nom)==nom_execo.end())//si ce nom n'est pas dans la liste des execo
   nom_execo.push_back(nom);//alors on l'ajoute
    }
  }
  return compteur>1;//retourne vrai si plus d'un nom a obtenu la mention majoritaire
}


std::string scrutin::mentionmini(){
  int minimum=5;//5=à rejeter
  std::string nommini;
  for(auto nom:vec_nomscandidats)//pour chaque nom de candidat
    if(mentionchacun[nom]<minimum){//si ce candidat a une meilleure mention majoritaire
      minimum=mentionchacun[nom];//alors on retient cette mention
      nommini=nom;//et on retient aussi le nom ce candidat
    }
  return nommini;//retourne le nom du candidat ayant la meilleure mention majoritaire
}

quelqu'un a une idée?



emmesse
Membre Naturel
Messages: 14
Enregistré le: 08 Oct 2018, 08:48

Re: scrutin jugement majoritaire

par emmesse » 07 Juin 2024, 22:34

j'ai corrigé le programme pour qu'il calcule nbvotants avant la mention majoritaires des candidats
Code: Tout sélectionner
//scrutin.cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#include "scrutin.hpp"
#include "enumetstruct.hpp"

scrutin::scrutin(std::string nomfichier):S(nomfichier){
  S.anasynt(vec_nomscandidats,vec_listebulletins);//construit les candidats et les bulletins à partir du texte d'entrée
}

void scrutin::elu(){
  for(auto &struct_bulletin:vec_listebulletins){//pour chaque bulletin
    absentarejeter(struct_bulletin);//on attribue la mention "à rejeter" aux candidats absent du bulletin
  }
  nomsvalides();//vérifie que les noms sont constitués par un ensemble de mot débutant par une majuscule et éventuellement suivi de minuscules
  unjugementparcandidatetbulletin();//vérifie que, sur un bulletin de vote, un candidat n'a pas plus d'une mention
 
  if(vec_listebulletins.size()!=0){//si la liste des bulletins n'est pas vide
    calculscores();
    afficherscores();
    nbvotants=vec_listebulletins.size();
    mentionmajoritaires();//calcule la mention majoritaire de chaque candidat
    garder_meilleure_mention();//supprime les candidate n'ayant pas la meilleure mention majoritaire
    while(nbvotants>1 && execo()){//La fonction execo retourne vrai si plus d'un candidat a la meilleure mention majoritaire
      for(auto nom:vec_nomscandidats)
   scores[nom][mentionchacun[nom]]--;//on décrémente la mention majoritaire dans les scores, pour chaque candidat
      nbvotants--;//le nombre de votant est alors décrémenté
      mentionmajoritaires();//calcule la nouvelle mention majoritaire de chaque candidat
      garder_meilleure_mention();//on supprime les candidats qui n'ont pas la meilleure mention majoritaire
    }
    if(execo()){
      std::cout<<"Ex æquo entre ";
      for(size_t i=0;i<nom_execo.size();i++){
   std::cout<<nom_execo[i];
   if(i+1<nom_execo.size())
     std::cout<<" et ";
      }
      std::cout<<std::endl;
    }
    else
      std::cout<<"Le candidat élu est "<<mentionmini()<<std::endl;
  }
  else
    std::cout<<"Pas de buletin valide"<<std::endl;
}

void scrutin::garder_meilleure_mention(){
  int mention_min=5;//à rejeter
  for(auto nom:vec_nomscandidats)
    if(mentionchacun[nom]<mention_min)
      mention_min=mentionchacun[nom];
  for(size_t i=0;i<vec_nomscandidats.size();i++){
    std::string nom=vec_nomscandidats[i];
    if(mentionchacun[nom]!=mention_min){
      vec_nomscandidats.erase(vec_nomscandidats.begin()+i);
      mentionchacun.erase(nom);
      scores.erase(nom);
      i=-1;
    }
  }
}

void scrutin::unjugementparcandidatetbulletin(){
  bool ecraser=false;
  for(size_t numbulletin=0;numbulletin<vec_listebulletins.size();numbulletin++){
    for(int jugement=0;jugement<6;jugement++)
      for(auto nom:vec_listebulletins[numbulletin].candidatmention[jugement])
   for(int compare=jugement+1;compare<6;compare++){
     std::vector<std::string>listenoms=vec_listebulletins[numbulletin].candidatmention[compare];
     if(find(listenoms.begin(),listenoms.end(),nom) != listenoms.end()){
       std::cerr<<"Présence d'un nom ayant plusieur mention dans le même bulletin. Bulletin nul"<<std::endl;
       ecraser=true;
     }
   }
    if(ecraser){
      vec_listebulletins.erase(vec_listebulletins.begin()+numbulletin);
      numbulletin--;
      ecraser=false;
    }
  }
}

void scrutin::mentionmajoritaires(){
  for(auto nomcandidat:vec_nomscandidats){
    long double mention=0.0;
    int jugement;
    for(jugement=0;jugement<6;jugement++){
      mention+=(long double)scores[nomcandidat][jugement]/(long double)nbvotants;
      if(mention>=0.5)
   break;
    }
    mentionchacun[nomcandidat]=jugement;
  }
}

bool scrutin::absent(occurence_bulletin const &struct_bulletin,std::string nom){
  for(int i=0;i<6;i++){
    std::vector<std::string>listenomsmention;
    listenomsmention=struct_bulletin.candidatmention[i];
    if(find(listenomsmention.begin(),listenomsmention.end(),nom) != listenomsmention.end())
      return false;
  }
  return true;
}

void scrutin::absentarejeter(occurence_bulletin &struct_bulletin){
  for(auto nom:vec_nomscandidats)
    if(absent(struct_bulletin,nom))
      struct_bulletin.candidatmention[5].push_back(nom);
}

void scrutin::nomsvalides(){
  for(size_t numbulletin=0;numbulletin<vec_listebulletins.size();numbulletin++){
    for(int jugement=0;jugement<6;jugement++){
      std::vector<std::string>listenoms;
      listenoms=vec_listebulletins[numbulletin].candidatmention[jugement];
      for(auto nom:listenoms)
   if(find(vec_nomscandidats.begin(),vec_nomscandidats.end(),nom)==vec_nomscandidats.end()){
     std::cerr<<"\""<<nom<<"\""<<" absent de la liste des candidats. Bulletin nul"<<std::endl;
     vec_listebulletins.erase(vec_listebulletins.begin()+numbulletin);
     if(numbulletin!=0){
       numbulletin--;
     }
   }
    }
  }
}

void scrutin::calculscores(){
  for(auto struct_bulletin:vec_listebulletins){
    for(int jugement=0;jugement<6;jugement++)
      for(auto nomcandidat:struct_bulletin.candidatmention[jugement])
   scores[nomcandidat][jugement]++;
  }
}

void scrutin::afficherscores(){
  unsigned int nbvotantsdansafficher=vec_listebulletins.size();
  for(auto nom:vec_nomscandidats){
    std::cout<<nom<<":"<<std::endl;
    for(int i=0;i<6;i++){
      switch(i){
      case 0:
   std::cout<<"très bien: "<<(long double)scores[nom][i]/(long double)nbvotantsdansafficher*100<<"%";
   break;
      case 1:
   std::cout<<"bien: "<<(long double)scores[nom][i]/(long double)nbvotantsdansafficher*100<<"%";
   break;
      case 2:
   std::cout<<"assez bien: "<<(long double)scores[nom][i]/(long double)nbvotantsdansafficher*100<<"%";
   break;
      case 3:
   std::cout<<"passable: "<<(long double)scores[nom][i]/(long double)nbvotantsdansafficher*100<<"%";
   break;
      case 4:
   std::cout<<"insuffisant: "<<(long double)scores[nom][i]/(long double)nbvotantsdansafficher*100<<"%";
   break;
      case 5:
   std::cout<<"à rejeter: "<<(long double)scores[nom][i]/(long double)nbvotantsdansafficher*100<<"%";
   break;
      }
      std::cout<<std::endl;
    }
    std::cout<<std::endl;
  }
}
   

bool scrutin::execo(){
  nom_execo.clear();
  int minimum=5;//5=à rejeter
  for(auto nom:vec_nomscandidats)
    if(mentionchacun[nom]<minimum)//si le candidat(nom) a une meilleure mention majoritaire
      minimum=mentionchacun[nom];//alors cette mention est retenue
  int compteur=0;
  for(auto nom:vec_nomscandidats){
    if(mentionchacun[nom]==minimum){
      compteur++;//compte combien de candidats ont la meileure mention majoritaire
      if(std::find(nom_execo.begin(),nom_execo.end(),nom)==nom_execo.end())//si ce nom n'est pas dans la liste des execo
   nom_execo.push_back(nom);//alors on l'ajoute
    }
  }
  return compteur>1;//retourne vrai si plus d'un nom a obtenu la mention majoritaire
}


std::string scrutin::mentionmini(){
  int minimum=5;//5=à rejeter
  std::string nommini;
  for(auto nom:vec_nomscandidats)//pour chaque nom de candidat
    if(mentionchacun[nom]<minimum){//si ce candidat a une meilleure mention majoritaire
      minimum=mentionchacun[nom];//alors on retient cette mention
      nommini=nom;//et on retient aussi le nom ce candidat
    }
  return nommini;//retourne le nom du candidat ayant la meilleure mention majoritaire
}

La question est la même: mon programme fait-il la même chose que l'algorithme récursif de M Balinski et M Laraki?
(je précise que je l'ai testé et il me paraît donner les bons résultats)

emmesse
Membre Naturel
Messages: 14
Enregistré le: 08 Oct 2018, 08:48

Re: scrutin jugement majoritaire

par emmesse » 15 Juin 2024, 20:13

je rappelle le jugement majoritaire:
https://fr.wikipedia.org/wiki/Jugement_majoritaire
on a le map score qui indique le nombre d'électeurs qui ont donné un jugement à chaque candidat.
Code: Tout sélectionner
std::map<std::string,int[6]>scores;

par exemple, si on a les bulletins:
Code: Tout sélectionner
candidats Toto,Titi,Tata

bulletins

tresbien Tata
bien Titi,Toto
assezbien personne
passable personne
insuffisant personne
arejeter personne
finbulletin

tresbien personne
bien Toto
assezbien personne
passable Titi
insuffisant personne
arejeter personne
finbulletin

tresbien Titi
bien personne
assezbien Tata
passable personne
insuffisant Toto
arejeter personne
finbulletin

tresbien personne
bien personne
assezbien Tata
passable personne
insuffisant Toto
arejeter personne
finbulletin
fin

le map scores sera:
Code: Tout sélectionner
scores = std::map with 3 elements = { ["Tata"] = {1, 0, 2, 0, 0, 1},
                                      ["Titi"] = {1, 1, 0, 1, 0, 1},
                  ["Toto"] = {0, 2, 0, 0, 2, 0}
                }


la ligne ["Tata"] = {1, 0, 2, 0, 0, 1} signifie:
Code: Tout sélectionner
Tata a 1 électeur qui le juge très bien, 0 bien, 2 assezbien, 0 passable, 0 insuffisant et 1 à rejeter

il y a quatre électeurs.
1 électeur juge TB pour Tata
1+(le nombre d’électeurs B pour Tata,qui est 0)=1+0 électeur juge TB ou B pour Tata
1+(le nombre d’électeurs AB pour Tata=2)=1+2=3 électeurs juge TB,B ou AB pour Tata
3 étant supérieur ou égal à 4/2(=2), le jugement majoritaire de Tata est AB (assez bien).
de même le jugement majoritaire de Titi et Toto est tous les deux bien
On le retrouve dans la donnée mentionchacun:
Code: Tout sélectionner
std::map<std::string,int>mentionchacun
mentionchacun = std::map with 3 elements = {["Tata"] = 2, ["Titi"] = 1,
  ["Toto"] = 1}

chaque valeur de mentionchacun correspond à un jugement.
2 signifie assez bien et 1 signifie bien (le jugement très bien est 0)

On ne s’intéresse alors qu'aux score de Titi et Toto car ils ont tous deux le jugement majoritaire "bien"
voici un diagramme illustrant cette élection:
Image
le jugement majoritaire des candidats correspond au jugements sur la ligne jaune. on supprime alors les candidats qui n'ont pas le meilleur jugement majoritaire, on supprime la ligne jaune, comme dans un tableur, et on refait la ligne jaune dans le nouveau diagramme
Image
Si on supprime cette ligne et que l'on recalcule les jugements majoritaire, cela ne correspond-il pas à décrémenter le nombre d'électeurs pour chaque jugement majoritaires et pour chaque candidats, puis décrémenter globalement le nombre d’électeurs, puis recalculer les jugements majoritaires?
Code: Tout sélectionner
 for(auto nom:vec_nomscandidats)//vec_nomscandidats est la liste des nom des candidats
   scores[nom][mentionchacun[nom]]--;
 nbvotants--;

(au passage, l'élu est titi)

qu'en pensez-vous?

 

Retourner vers ⚜ Salon Mathématique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 4 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite