Discussion :

[Quintoux]

Bonjour,

Voici un problème qui (je pense) n'a jamais été posé ici.

Joueur passionné de Pétanque, il existe depuis quelque temps une mode à un nouveau type de concours qui s'appelle le Concours en Doublette à la Mêlée Tournante en 4 parties.

J'explique le problème :

* Peu importe le nombre de joueurs mais on va quand même commencer avec un minimum de 24 joueurs.
* A chaque partie, chaque joueur change de partenaire (mais le tirage est réalisé AVANT le début du concours et à l'issue des inscriptions).
* Le concours se base sur des parties en Doublettes (équipe de 2 joueurs contre 2 joueurs) mais dans le cas ou il y aurait un nombre IMPAIR de joueurs, une ou plusieurs équipes se composerait de 3 joueurs (Triplette)
* Tous les joueurs doivent jouer à Chaque partie (Si par exemple, il y a 30 joueurs, alors on ne formera pas 15 Doublettes car cela fera 7 matchs entre 2 équipes et la dernière équipe ne jouerait pas donc on formera AUTOMATIQUEMENT un nombre PAIR d'équipe, ici, il s'agirait de 12 DOUBLETTES et 2 TRIPLETTES)
* Tous les joueurs vont jouer 4 parties
* Dans le cas ou des TRIPLETTES apparaissent, (1, 2 ou 3 maximum par parties), s'il y en a 2, elles se rencontrent et la 3ème jouera contre une Doublette.
* Lors des 4 parties, s'il y a des TRIPLETTES alors une même personne ayant déjà joué en TRIPLETTE ne retombera pas en TRIPLETTE à moins que tout le monde ait déjà intégré une triplette.
* Personne ne DOIT REJOUER AVEC le même joueur
-----------------------------------------------------------------
Tous ces critères précisés ci-dessus, j'ai réussi à les programmer et donc je parviens à générer toutes les parties que je veux à l'avance .... ainsi, lorsque tous les joueurs sont inscrit, chacun vient tirer au hasard son numéro et il connait alors ses partenaires et adversaires pour le concours en 4 parties.
-----------------------
Mon soucis est le suivant, le principe de ce concours est d'ajouter une CONDITION : NE PAS REJOUER CONTRE UN MÊME ADVERSAIRE (ni contre une personne ayant été partenaire).

Je sais que cette condition n'est pas possible si on prend moins de 32 joueurs car j'ai lu sur un site qu'il fallait décomposer les parties en SOUS-GROUPES mais je voulais savoir si quelqu'un pouvait comprendre le procédé et expliquer les conditions nécessaires pour traduire toutes ces conditions en ALGORITHME ou bien en Mathématiques avec groupes.

PS : Je suis à votre entière disposition pour de plus amples informations par mail à pierre.guiraud@hotmail.fr

Merci d'avance et à bientot

[Invité]

Bonjour,
Amusant votre problème.
Si j'ai bien compris, tous les problèmes de constitution d'équipe sont résolus, SAUF

NE PAS REJOUER CONTRE UN MÊME ADVERSAIRE (ni contre une personne ayant été partenaire).

A première vue, cela na parait pas trop compliqué à rajouter.

Je ne suis pas spécialiste, mais je suppose qu'il n'y a pas d'éliminatoires. C'est à dire que tous les joueurs jouent exactement le même nombre de parties (4 si j'ai bien compris).

Je pense à l'algorithme dit "glouton", qui consiste à tester toutes le possibilités tant qu'on n'a pas trouvé la bonne.

Une fois le système trouvé, il suffira d'imprimer la constitution des équipes pour chaque nombre d'inscrits.

[Quintoux]

Oui c'est çà ... les conditions sont les suivantes :

1) Tous les joueurs jouent à chaque parties (ceci permet donc de créer des doublettes et/ou des triplettes selon le nombre de joueurs ... pour mes tests, je fais entre 24 et 128 joueurs)
2) Le concours s'organise en 4 parties
3) Aucun JOUEUR ne doit rejouer AVEC un même JOUEUR
4) Aucun JOUEUR ne doit rejouer CONTRE un même JOUEUR (dans la mesure du possible car si on fait baisser le nombre de joueurs jusqu'à 16, je pense que cette condition ne pourra être réalisé)
5) Si des triplettes sont présentes, il faut que les joueurs n'en fassent qu'une dans la mesure du possible (et si tout le monde a déjà intégré une triplette alors certains en intègreront une seconde).
6) Si 2 triplettes sont présentes, alors elles se rencontrent

Voilà pour les explications.

PS : Peux-tu m'en dire un peu plus sur l 'algorithme du glouton car je ne connais pas

PS : Je peux fournir un ou plusieurs exemples pour donner des précisions.

[Invité]

Pour être tout à fait franc, je connais le terme depuis hier. Voici la définition de Wikipédia.

Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l'espoir d'obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton. Dans les cas où l'algorithme ne fournit pas systématiquement la solution optimale, il est appelé une heuristique gloutonne.

Je vais prendre une exemple. La théorie des quatre couleurs dit qu'étant donné un ensemble de zones contigües comme le sont les département français (hord enclaves), il est possible de les colorier avec seulement 4 couleurs de façon que 2 départements voisins aient des couleurs différentes.
Si j'applique l'algorithme glouton, je vais appliquer une couleur sur un département, puis un autre sur le voisin, etc. A un moment ca ne marchera plus. Donc je change la couleur sur le troisième et je recommence. Avec cette méthode, on est sûr d'y arriver, mais dans combien de temps?
Avec un algorithme non-glouton, on organise un graphe.
La préparation de ce graphe dure 30 s, et la recherche en elle même non mesurable parce qu'immédiat.
Pour mémoire, c'est une théorie, parce qu'à ma connaissance, on n'a encore pas réussi à le démontrer.

A mon avis pour votre problème, vous faites deux structures

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Joueur
{
  char *Nom
  int Num;
  int Partenaire[2];  // pour prévoir les triplettes
  int Adversaire[12]; // maxi 4 parties de 3 advervaires  
};
struct Partie
{
  Joueur EquipeA[3];
  Joueur EquipeB[3];
}
// et ensuite vous bouclez jusqu'à trouver une solution

Au départ vous créez un nouvelle partie. Le premier coup, ça marche toujours.
Pour les suivantes, vous vérifiez avant de la créer si les conditions sont satisfaites. Sinon, vous changez un joueur qui doit encore faire au moins une partie.
Naturellement, c'est un peu lourd, d'où le nom de glouton, mais j'imagine pas d'algorithme plus intelligent.
Naturellement aussi, on suppose que le problème est possible, donc n'est valable qu'au delà de 32 joueurs.
Si il y a moins de 32 joueurs, il y a une condition qui ne doit pas être testée.

[Quintoux]

Bon, OK

Merci pour ces précisions.

Je vais voir de mon coté ce que ca peut donner

[Invité]

bonjour,

sauf erreur de compréhension du problème et de codage , j'ai calculé via mon algo brut de pomme pour un nombre de joueurs entre 12 et 128 :

• Nb de joueurs pour avoir 4 parties sans doublon (13 * x)

Code :

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

1
2
3
4
5
6
7
8
9
10
 
Nb Joueurs:  13             Nb match: 13  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  26             Nb match: 26  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  39             Nb match: 39  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  52             Nb match: 52  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  65             Nb match: 65  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  78             Nb match: 78  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  91             Nb match: 91  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  104            Nb match: 104 Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  117            Nb match: 117 Nb triplettes: 0            Max Triple par joueur: 0

• Nb de joueurs pour avoir 3 parties sans doublon

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
 
Nb Joueurs:  12             Nb match: 9   Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  20             Nb match: 14  Nb triplettes: 2            Max Triple par joueur: 1
Nb Joueurs:  22             Nb match: 15  Nb triplettes: 3            Max Triple par joueur: 1
Nb Joueurs:  24             Nb match: 18  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  36             Nb match: 27  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  48             Nb match: 36  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  58             Nb match: 40  Nb triplettes: 7            Max Triple par joueur: 1
Nb Joueurs:  60             Nb match: 45  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  72             Nb match: 54  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  84             Nb match: 63  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  96             Nb match: 72  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  100            Nb match: 63  Nb triplettes: 24           Max Triple par joueur: 2
Nb Joueurs:  108            Nb match: 81  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  110            Nb match: 76  Nb triplettes: 13           Max Triple par joueur: 1
Nb Joueurs:  120            Nb match: 90  Nb triplettes: 0            Max Triple par joueur: 0
Nb Joueurs:  126            Nb match: 80  Nb triplettes: 29           Max Triple par joueur: 2

Voici un exemple de parties pour 13 joueurs et 4 parties par joueur:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
partie n°1    2-3-4-1
partie n°2    5-6-7-2
partie n°3    5-8-9-3
partie n°4    5-10-11-4
partie n°5    1-12-13-5
partie n°6    1-8-10-6
partie n°7    1-9-11-7
partie n°8    2-11-12-8
partie n°9    2-10-13-9
partie n°10   3-7-12-10
partie n°11   3-6-13-11
partie n°12   4-6-9-12
partie n°13   4-7-8-13

Exemple pour 20 joueurs avec triplettes mais seulement 3 parties par joueur

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
 
partie n°1    2-3-4-5-6-1
partie n°2    8-9-10-11-12-7
partie n°3    1-13-14-8
partie n°4    1-15-16-9
partie n°5    2-13-15-10
partie n°6    2-14-16-11
partie n°7    3-13-16-12
partie n°8    3-7-15-14
partie n°9    4-7-18-17
partie n°10   5-8-19-18
partie n°11   4-9-20-19
partie n°12   5-10-17-20
partie n°13   11-17-19-6
partie n°14   6-18-20-12

Arrivez-vous aux mêmes résultats ?

Cordialement,

Robert

[Quintoux]

sauf erreur de compréhension du problème et de codage , j'ai calculé via mon algo brut de pomme pour un nombre de joueurs entre 12 et 128 :

Bonjour,

Merci de votre recherche mais je pense que vous n'avez pas tout compris car j'ai rapidement regardé votre solution et je vois que vous avez oublié des détails dans le probleme.

En fait, c'est un concours de pétanque donc tout le monde doit participer à la 1ere partie, puis à la 2nde, 3eme et enfin à la 4eme.

Ainsi, il faut automatiquement le meme nombre de matchs par parties et ainsi on a X matchs à la partie 1, 2,3 et 4 donc voici un exmple simple mais précis avec 32 joueurs :

PARTIE 1
1 2 vs 3 4
5 6 vs 7 8
9 10 vs 11 12
13 14 vs 15 16
17 18 vs 19 20
21 22 vs 23 24
25 26 vs 27 28
29 30 vs 31 32

PARTIE 2
1 6 vs 11 16
5 10 vs 15 20
9 14 vs 19 24
13 18 vs 23 28
17 22 vs 27 32
21 26 vs 31 4
25 30 vs 3 8
29 2 vs 7 12

PARTIE 3
1 10 vs 19 28
5 14 vs 23 32
9 18 vs 27 4
13 22 vs 31 8
17 26 vs 3 12
21 30 vs 7 16
25 2 vs 11 20
29 6 vs 15 24

PARTIE 4
1 14 vs 7 20
5 18 vs 11 24
9 22 vs 15 28
13 26 vs 19 32
17 30 vs 23 4
21 2 vs 27 8
25 6 vs 31 12
29 10 vs 3 16

Ainsi, ici tout le monde joue à chaque partie et les conditions sont respectées :

Personne ne rejoue avec un MEME partenaire
Personne ne rejoue contre un MEME adversaire

(evidemment, ici, c'est le cas le plus simple car pas de TRIPLETTES mais je souhaite tout automatiser pour créer mes graphiques pour un nombre quelconsue de participants entre 16 et 128).

Merci d'avance

[fallobill]

Bonjour, j'organise des concours tous les vendredis soir et votre programme m'intéresse réellement. Avez-vous résolu votre problème, car j'ai le même et je suis obligé de faire les tirages à la main avec des pions

sportivement

----------------------------------------

Bonjour,

Merci de votre recherche mais je pense que vous n'avez pas tout compris car j'ai rapidement regardé votre solution et je vois que vous avez oublié des détails dans le probleme.

En fait, c'est un concours de pétanque donc tout le monde doit participer à la 1ere partie, puis à la 2nde, 3eme et enfin à la 4eme.

Ainsi, il faut automatiquement le meme nombre de matchs par parties et ainsi on a X matchs à la partie 1, 2,3 et 4 donc voici un exmple simple mais précis avec 32 joueurs :

PARTIE 1
1 2 vs 3 4
5 6 vs 7 8
9 10 vs 11 12
13 14 vs 15 16
17 18 vs 19 20
21 22 vs 23 24
25 26 vs 27 28
29 30 vs 31 32

PARTIE 2
1 6 vs 11 16
5 10 vs 15 20
9 14 vs 19 24
13 18 vs 23 28
17 22 vs 27 32
21 26 vs 31 4
25 30 vs 3 8
29 2 vs 7 12

PARTIE 3
1 10 vs 19 28
5 14 vs 23 32
9 18 vs 27 4
13 22 vs 31 8
17 26 vs 3 12
21 30 vs 7 16
25 2 vs 11 20
29 6 vs 15 24

PARTIE 4
1 14 vs 7 20
5 18 vs 11 24
9 22 vs 15 28
13 26 vs 19 32
17 30 vs 23 4
21 2 vs 27 8
25 6 vs 31 12
29 10 vs 3 16

Ainsi, ici tout le monde joue à chaque partie et les conditions sont respectées :

Personne ne rejoue avec un MEME partenaire
Personne ne rejoue contre un MEME adversaire

(evidemment, ici, c'est le cas le plus simple car pas de TRIPLETTES mais je souhaite tout automatiser pour créer mes graphiques pour un nombre quelconsue de participants entre 16 et 128).

Merci d'avance

[Invité]

bonjour,

Sauf erreur, ci-joint une solution pour les cas simples entre 20 et 128 joueurs, 256 joueurs.

Le cas d'une ou des triplettes n'est pas traité...

[MARGAR]

Bonjour le forum,

Serait-il possible d'obtenir le même résultat avec des Triplettes ?

Merci d'avance
Bonne journée

margar

[juanito8300]

Bonsoir,
Faisant partie d'une associaition et organisant des concours de pétanque régulièrement
je recherche la meme chose que ci-dessus mais pour des triplettes et avec 3 parties a partie de 40 joueurs jusqu'a 100 si possible et si suivant le nombre de joueurs ce n'est pas possible mathématiquement de n'avoir que des triplettes les doublettes sont acceptés mais vraiment s'il n'y a pas moyen de faire autrement et il ne faut pas sauf impossibilité que les meme joueurs jouent ensemble ou se rencontre 2 fois sur les 3 parties.

On fait 2 groupes les tireurs et les pointeurs de sort que dans chaque doublette ou triplette il y a toujours 1 tireur

faire la meme chose pour des doublettes mais de 20 jusqu'à 50 joueurs

Est- ce possible d'avoir un logiciel pour me faire les tirages au sort sur place?

Pour les calculs nous on prend par exemple: les joueurs gagnent 13 a 5 les gagnants ont 13+8 21 points et les perdants ont 5 points, on ajoute les points des 3 parties et les 4 meilleurs tireurs et les 4 meilleurs pointeurs sont qualifiés pour disputer les demi-finales et finales.

Les demi finalistes sont tirés au sort mais reste les meme pour la Finale.

Est-ce possible d'avoir un logiciel qui peut me faire ca?
Merci!!

en espérant que vous pourrez m'aider§