Discussion :

[emmesse]

Bonjour,

voici le scrutin à jugement majoritaire:

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

(je rappelle que les URL sont faites pour les ouvrir)

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, et le meilleur, 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 que le meilleur jugement est attribué à plusieurs candidats, on supprime les autres candidats, 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 cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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_exaequo;//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 exaequo();
  std::string mentionmini();
};
#endif

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#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 && exaequo()){//La fonction exaequo 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(exaequo()){
      std::cout<<"Ex æquo entre ";
      for(size_t i=0;i<nom_exaequo.size();i++){
	std::cout<<nom_exaequo[i];
	if(i+1<nom_exaequo.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;// 5= mention "à 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);// on attribue la mention "à rejeter" aux absent du bulletin de vote
}
 
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::exaequo(){
  nom_exaequo.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_exaequo.begin(),nom_exaequo.end(),nom)==nom_exaequo.end())//si ce nom n'est pas dans la liste des exaequo
	nom_exaequo.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
}

Ce code est-il équivalent à l'algorithme récursif de M Balinski et M Laraki?

pensez-vous que c'est assez exact pour que je puisse le mettre dans un billet du blog?

[tbc92]

J'ai peur que tu n'aies pas de réponse. Relire le code de quelqu'un d'autre est toujours difficile, et ce programme semble relativement long (tout est relatif, évidemment).

J'ai lu vraiment en diagonale, et j'ai vu qu'il y avait à beaucoup d'endroits le nombre 5 (note la plus basse qu'on peut donner). Si on veut ajuster et dire que les notes peuvent aller de 0 à 6, il faut donc faire plusieurs interventions. Ce n'est pas terrible.
Pour en dire plus, il faut vraiment fournir un effort plus important... pas le courage.

[emmesse]

on a le map score qui indique le nombre d'électeurs qui ont donné un jugement à chaque candidat.

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

std::map<std::string,int[6]>scores;

par exemple, si on a les bulletins:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
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 :

Sélectionner tout - Visualiser dans une fenêtre à part

Tata a 1 électeur qui le juge très bien, 0 bien, 2 assez bien, 0 passable, 0 insuffisant et 1 à rejeter

il y a quatre électeurs. La moitié en comptent 2.
1 électeur juge TB pour Tata
0 électeur juge B pour Tata, ce qui fait que 1+0=1 électeur juge TB (très bien) ou B (bien) pour Tata.
2 electeurs jugent AB pour Tata, on a donc 1+2=3 électeurs qui jugent TB, B ou AB (assez bien) pour Tata.
3 étant supérieur ou égal à 2 (la moitié des électeurs), le jugement majoritaire de Tata est AB.
de même le jugement majoritaire de Titi et Toto est bien pour eux deux.
On le retrouve dans la donnée mentionchacun:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
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" alors que Tata a le jugemente "assez bien"
voici un tableau illustrant cette élection:

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, et on refait la ligne jaune dans le nouveau tableau

Si on supprime cette ligne, que l'on supprime les candidat n'ayant pas le meilleur jugement, et que l'on recalcule les jugements majoritaire, cela ne correspond-il pas à décrémenter le nombre d'électeurs pour chaque jugement majoritaires, supprimer les candidat n'ayant pas le meilleur jugement majoritaire, puis décrémenter globalement le nombre d’électeurs, puis recalculer les jugements majoritaires?

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 for(auto nom:vec_nomscandidats)
	scores[nom][mentionchacun[nom]]--;
nbvotants--;

(au passage, l'élu est Titi)

qu'en pensez-vous?