IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Rotations pour un tournoi


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2020
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 19
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : août 2020
    Messages : 8
    Points : 1
    Points
    1
    Par défaut Rotations pour un tournoi
    Bonjour,
    (Si vous avez des questions, je peux préciser ma demande.)

    Pour un tournoi de jeu,

    Je souhaite organiser la rotation des joueurs:
    * les ordres de tour doivent être également répartis
    * chaque joueur devra rencontrer le plus de joueurs différents

    Exemple avec 10 joueurs, numérotés de 1 à 10, et des tables de 4 joueurs.
    Ordre de jeu: chaque joueur sera N fois 1er, N fois 2e, N fois 3e, N fois 4e

    Tour 1 (tables de jeu avec ordre de jeu)
    Table 1: 1, 2, 3, 4
    Table 2: 5, 6, 7, 8
    En pause: 9, 10

    Tour 2
    9 et 10 entrent en jeu.
    Une rotation triviale (du genre chaque joueur se décale d'une place) ne convient pas, trop de joueurs rencontreraient les mêmes.

    Une idée d'algorithme à utiliser svp?

    Si vous avez des questions, je peux préciser ma demande.

    Merci d'avance.

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 096
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 3 096
    Points : 7 075
    Points
    7 075
    Par défaut
    A priori, l'énoncé est incomplet.

    Scénario 1 : Au 2ème tour, on cherche à optimiser un certain indicateur, au 3ème tour, on cherche à optimiser le même indicateur, au 4ème tour, idem ...
    Scénario 2 : On sait d'entrée qu'on va faire n tours, et on veut optimiser un certain indicateur 'global'.

    L'indicateur en question, c'est plus ou moins un nombre de doublons.
    La solution optimale pour le scénario 1 ne sera très certainement pas la solution optimale pour le scénario 2.
    Le scénario 1 est plus facile à résoudre. On a une succession de petits problèmes, au lieu d'un gros problème.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2020
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 19
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : août 2020
    Messages : 8
    Points : 1
    Points
    1
    Par défaut
    Effectivement, l'énoncé est incomplet.
    Résoudre un problème consiste d'abord à bien le poser.
    C'est parce que je peine à déterminer les facteurs que je sèche sur la solution.

    J'ajoute ces éléments :
    * il faut un certain nombre de tours minimal pour que le classement du tournoi ait une certaine validité. En ronde suisse c'est log J , arrondi à l'entier supérieur. (J nombre de joueurs)
    * Ici, 4 ordres, donc N est un multiple de 4

    J'ai donc peur qu'il faille aller vers le scénario 2, en tout cas, pour le cas général.

    Dans certains cas, pas d'ordre de jeu, moins de contrainte pour N.
    Explorons d'abord le scénario 1 pour ce cas.

    L'élément à optimiser est déterminé par
    * maximiser le nombre de confrontations entre joueurs différents
    * minimiser l'ecart-type du nombre de tours joué par chaque joueur

    Cela vous semble-t-il plus clair?

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 096
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 3 096
    Points : 7 075
    Points
    7 075
    Par défaut
    Tu parles de rondes suisses.
    Il me semble que dans un système de rondes suisses, on fait en sorte que joueurs les mieux classés après les tours écoulés jouent les uns contre les autres.
    Et donc, on ne peut pas décider à l'avance de toute la mise en place, cette mise en place dépend des résultats des premiers tours.

    Tu dis que l'élément à optimiser est :
    *A* maximiser le nombre de confrontations entre joueurs différents
    *B* minimiser l'ecart-type du nombre de tours joué par chaque joueur

    Ok. Dans ton premier message, tu ajoutais un autre critère : Si à la table 1, on a (1,2,3,4), ou si on a (1,2,4,3), c'est différent. C'est effectivement différent, ou pas ?
    Ca nous donne un 3ème objectif :
    *C* minimiser l'écart-type du nombre de fois où un joueur joue à la même place. (à reformuler ...)

    Quand on a 2 objectifs à maximiser (et pire quand on en a 3), il faut définir des règles pour concilier ces 3 objectifs.
    Ici, la fonction B semble prioritaire : on ne peut pas avoir un joueur qui va être 3 fois en repos, alors qu'un autre serait une seule fois en repos.
    Par contre, entre les objectifs A et C, c'est un peu plus compliqué.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2020
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 19
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : août 2020
    Messages : 8
    Points : 1
    Points
    1
    Par défaut
    J'ai indiqué que l'ordre de jeu était impérativement également reparti entre les joueurs.
    Dans le cas général.
    Mais dans certains cas, elle n'existe pas.

    J'ai indiqué que, dans un premier temps, on pouvait se concentrer sur les cas ou cette contrainte n'existait pas.
    Avez-vous une piste dans ce cas?

  6. #6
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 613
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 613
    Points : 11 525
    Points
    11 525
    Par défaut
    Bonjour

    https://en.wikipedia.org/wiki/Duplic...idge_movements
    Dans ce lien, ce sont les tournois en individuel qui t'intéressent.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  7. #7
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2020
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 19
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : août 2020
    Messages : 8
    Points : 1
    Points
    1
    Par défaut
    Merci.

    Mais ça ne répond pas à la question.

    Dans Rainbow et Shomate Movements, le nombre de joueurs est un multiple de 4 (nombre de joueurs par table).
    Ma question indique que le nombre de joueurs est libre. Donc qu'à chaque tour, des joueurs peuvent être en pause.

  8. #8
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 613
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 613
    Points : 11 525
    Points
    11 525
    Par défaut
    La pause n'est-elle pas une table surnuméraire virtuelle ?
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  9. #9
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2020
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 19
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : août 2020
    Messages : 8
    Points : 1
    Points
    1
    Par défaut
    Sauf que cette table virtuelle n'est pas complète.

    En appliquant
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    Regular Rainbow Movement
    East players move UP TWO tables.
    South players move UP ONE table.
    West players move DOWN TWO tables.
    Boards move DOWN ONE table.
    On obtient

    ROUND...1
    1 2 3 4
    5 6 7 8
    9 10
    ROUND...2
    1 6 7
    2 3 8 9
    4 5 10
    ROUND...3
    5 2 3
    10 8 1
    9 6 7
    Soit 2 tables à 3 joueurs.
    Bref, ça ne fonctionne pas.

    Avec 12 joueurs par exemple,c'est OK.

    ROUND...1
    1 2 3 4
    5 6 7 8
    9 10 11 12
    ROUND...2
    1 6 7 12
    2 3 8 9
    4 5 10 11
    ROUND...3
    5 2 3 12
    10 11 8 1
    4 9 6 7

  10. #10
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 160
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 74
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 160
    Points : 2 224
    Points
    2 224
    Billets dans le blog
    9
    Par défaut Rotations pour un tournoi
    Bonjour,

    Il y a 10 joueurs. Or 11 est un nombre premier, qui admet pour racines primitives: 2, 6, 7, 8 .
    Les suites modulaires périodiques correspondantes ne permettraient-elles pas de définir l'organisation des tournois ?

    R = 2: uk = 1, 2, 4, 8, 5, 10, 9, 7, 3, 6 (1, 2 ...)
    R = 6: uk = 1, 6, 3, 7, 9, 10, 5, 8, 4, 2 (1, 6 ...) < suite rétrograde de la précédente >
    R = 7: uk = 1, 7, 5, 2, 3, 10, 4, 6, 9, 8 (1, 7 ...)
    R = 8: uk = 1, 8, 9, 6, 4, 10, 3, 2, 5, 7 (1, 8 ...) < suite rétrograde de la précédente >

    C'est une simple proposition.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  11. #11
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2020
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 19
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : août 2020
    Messages : 8
    Points : 1
    Points
    1
    Par défaut
    Citation Envoyé par Flodelarab Voir le message
    La pause n'est-elle pas une table surnuméraire virtuelle ?
    Comme indiqué, ça ne fonctionne pas, on obtient parfois des tables incomplètes.
    Je tente en vérifiant qu'elles sont complètes et en construisant de nouvelles tables si ce n'est pas le cas.
    ...
    Ça ne fonctionne pas.

    Citation Envoyé par wiwaxia Voir le message
    Il y a 10 joueurs. Or 11 est un nombre premier, qui admet pour racines primitives: 2, 6, 7, 8 .
    Les suites modulaires périodiques correspondantes ne permettraient-elles pas de définir l'organisation des tournois ?

    R = 2: uk = 1, 2, 4, 8, 5, 10, 9, 7, 3, 6 (1, 2 ...)
    R = 6: uk = 1, 6, 3, 7, 9, 10, 5, 8, 4, 2 (1, 6 ...) < suite rétrograde de la précédente >
    R = 7: uk = 1, 7, 5, 2, 3, 10, 4, 6, 9, 8 (1, 7 ...)
    R = 8: uk = 1, 8, 9, 6, 4, 10, 3, 2, 5, 7 (1, 8 ...) < suite rétrograde de la précédente >

    C'est une simple proposition.
    10 est un exemple.
    Ça doit fonctionner quelque soit le nombre de joueurs.

  12. #12
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 160
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 74
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 160
    Points : 2 224
    Points
    2 224
    Billets dans le blog
    9
    Par défaut Rotations pour un tournoi
    Citation Envoyé par Ogival Voir le message
    ... 10 est un exemple.
    Ça doit fonctionner quelque soit le nombre de joueurs.
    Il suffit de repérer le nombre premier immédiatement supérieur, et de considérer les suites correspondant à ses racines primitives.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  13. #13
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2020
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 19
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : août 2020
    Messages : 8
    Points : 1
    Points
    1
    Par défaut
    Citation Envoyé par wiwaxia Voir le message
    Il suffit de repérer le nombre premier immédiatement supérieur, et de considérer les suites correspondant à ses racines primitives.
    Et vous êtes sûr que ça fonctionne ?

  14. #14
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2020
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 19
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : août 2020
    Messages : 8
    Points : 1
    Points
    1
    Par défaut
    Citation Envoyé par Flodelarab Voir le message
    La pause n'est-elle pas une table surnuméraire virtuelle ?
    Comme indiqué, ça ne fonctionne pas.
    J'obtiens 2 tables de 3 joueurs.

    Je tente en traitant la liste complète des joueurs et je fais change les positions avec l'algo bridge.
    Ensuite, je prends les 4 1ers pour la 1ere table...
    Exemple : 2, 5, 7 , 1, 9 , 3 , 8 , 4 , 10 , 6 donne
    Table 1: 2, 5 , 6 , 1
    Table 2: 9 , 3 , 8 , 4
    Pause: 10 , 6

    ....
    Ça ne fonctionne pas.
    On affecte la même place à plusieurs joueurs.

  15. #15
    Membre éprouvé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    344
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 344
    Points : 1 209
    Points
    1 209
    Par défaut Modulo
    Bonjour,

    Les modulos simples ne peuvent pas fonctionner (de même que toute bijection) car au bout d'au plus 10 valeurs on retrouvera l'une de celle ci et la séquence recommencera à l'identique. L'organisation en groupe de 4 permet de doubler éventuellement les cas mais 20 ne font que 5 tables soit 2 tours seulement. Les modulos composés, par exemple sur la base d'un polynôme premier (par exemple 5z-2 + 3 Z-1 + 1), donneront des séquences plus variées mais ne garantiront pas l'absence de redondance locale.

    Une approche, à tester, pourrait être de transformer :
    • les carrés ab/cd en ac/bd des deux tables
    • puis d'intégrer la réserve en tête de tables tandis que les derniers de tables sont mis en réserve


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    1: 1 2 3 4    9  en  1 5 3 7    9  puis  2: 9 1 5 3   7  en  9 10 5 6   7 puis  3: 7 9 10 5   6
       5 6 7 8   10      2 6 4 8   10          10 2 6 4   8      1  2 3 4   8          8 1  2 3   4
    Ce n'est pas très glorieux mais cela permet de respecter l'homogénéité des pauses et un nombre de tours assez important (a priori 10).

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  16. #16
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 160
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 74
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 160
    Points : 2 224
    Points
    2 224
    Billets dans le blog
    9
    Par défaut Rotations pour un tournoi
    Bonjour,

    J'ai repensé à ce problème, et à une solution aléatoire.
    Si se présentent (N) joueurs devant intervenir dans un ordre différent (1, 2, 3 ou 4) au cours des parties successives, on peut imaginer un tableau de multiplets d'entiers
    (Date, Ordre1, Ordre2, Ordre3, Ordre4)
    initialisés à (0, 1, 2, 3, 4), et dont le rang identifie chaque joueur - par exemple l'ordre d'inscription.
    Rien n'interdit d'y ajouter son nom afin de faciliter l'impression des listes de compétition, mais cela n'intervient pas dans l'algorithme.

    Chaque équipe résulterait de l'appel aléatoire de 4 candidats, dont chacun devrait participer à 4 parties dans la même journée (ou disons la même période) et interviendrait obligatoirement dans des ordres de jeu différents, ce qui limite à (N = 4N/4) le nombre total de parties. On peut envisager ensuite une nouvelle séquence avec un nombre plus restreint de joueurs.
    Le tirage s'effectuerait par l'appel de la fonction Random(4N), qui retournerait la valeur d'une variable entière pseudo-aléatoire (a) située dans le domaine [0..(4N - 1)], et dont on pourrait déduire:
    # l'identifiant du joueur r = a DIV 4 ,
    # sa position dans la partie: p = 1 + (k MOD 4) .
    On éviterait le cumul accidentel de candidats et/ou d'ordres identiques lors de la constitution d'une équipe par le recours à une fonction booléenne Test4E(w, x, y, z) vérifiant que ses arguments entiers sont tous mutuellement différents.
    La convocation stricte de tous les candidats résulterait de la suppression des valeurs déjà sorties d'une liste d'entiers préalablement établie.

    Voici ce que donne un petit programme rédigé en Pascal, planifiant les 40 parties auxquelles participent 40 candidats, selon les restrictions définies plus haut:

    Nom : Tableau Résultats.png
Affichages : 117
Taille : 20,4 Ko

    Dans le volet gauche, l'appel des joueurs dans les 40 parties successives; au milieu la longueur de la liste d'entiers, amputée de 4 termes après la constitution d'une équipe; à droite, des résultats redondants permettant de vérifier que chaque joueur est intervenu 4 fois, et dans un ordre de jeu différent:
    a) à chaque appel, la date initialement nulle est augmentée de l'ordre d'affectation dans le jeu; la nouvelle valeur est par conséquent:
    0 + 1 + 2 + 3 + 4 = 10;
    b) la valeur de l'ordre du jeu est multipliée par 100: tout apparaît conforme à ce qui est attendu.

    Le contenu du fichier source se traduit sans peine dans votre langage habituel.

    Code Delphi : 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
     PROGRAM Tournoi;
     
     USES Crt, E_Texte;
     
     CONST Njoueur = 40; Nj4 = 4 * Njoueur;
     
     TYPE Tab_4NE = ARRAY[0..Nj4] OF Word;
          Tab_4E = ARRAY[1..4] OF Word;
          Joueur = RECORD  Date: Word;
                           OrdJ: Tab_4E  END;
          Tab_T = ARRAY[0..Njoueur - 1] OF Tab_4E;
          Tab_J = ARRAY[0..Njoueur - 1] OF Joueur;
     
     VAR Npart: Word;
         ListeN: Tab_4NE;
         ListeJ: Tab_J;
         ListeT: Tab_T;
     
     PROCEDURE Controle;
       CONST C1 = 35; L1 = 5; o = 7;
       VAR i: Byte; k: Word;
       BEGIN
         E(0015); Wt(C1 + 4, L1 - 3, 'Rang   Date        Ordres du jeu');
         FOR k:= 0 TO (Njoueur - 1) DO
           BEGIN
             E(0012); We(C1, L1 + k, k, o);
             E(0009); Write(ListeJ[k].Date:o); E(0014);
             WITH ListeJ[k] DO
               FOR i:= 1 TO 4 DO Write(OrdJ[i]:o)
           END;
         A_
       END;
     
     PROCEDURE EpurationLn(Ia, Ib, Ic, Id: Word;
                         VAR N_m: Word; VAR L_n: Tab_4NE);
       CONST Jmax = Nj4 - 1;
       VAR j, J1, Nm: Word;
       BEGIN
         J1:= 0;   WHILE (L_n[J1]<>Ia) DO Inc(J1);
         FOR j:= J1 TO Jmax DO L_n[j]:= L_n[j + 1];
         J1:= 0;   WHILE (L_n[J1]<>Ib) DO Inc(J1);
         FOR j:= J1 TO Jmax DO L_n[j]:= L_n[j + 1];
         J1:= 0;   WHILE (L_n[J1]<>Ic) DO Inc(J1);
         FOR j:= J1 TO Jmax DO L_n[j]:= L_n[j + 1];
         J1:= 0;   WHILE (L_n[J1]<>Id) DO Inc(J1);
         FOR j:= J1 TO Jmax DO L_n[j]:= L_n[j + 1];
         Nm:= N_m; N_m:= Nm - 4
       END;
     
     PROCEDURE Aff_IdJNmax(W: Tab_4E; Nm: Word);
       VAR i: Byte;
       BEGIN
         E(0011); FOR i:= 1 TO 4 DO Write(W[i]:5);
         E(0010); Write(Nm:10)
       END;
     
     PROCEDURE Aff_Np(k_: Word);
       CONST L1 = 4; o = 5;
       BEGIN
         IF (k_=1) THEN BEGIN
                          E(1015); Wt(2, L1 - 2, 'Partie      Joueurs');
                          Write('           Nmax');
                        END;
         E(0013); We(1, L1 + k_, k_, o)
       END;
     
     FUNCTION Test4E(w, x, y, z: Word): Bool;
       VAR Twxyz, Twyxz, Twzxy: Bool;
       BEGIN
         Twxyz:= ((w<>x) AND (y<>z));
         Twyxz:= ((w<>y) AND (x<>z));
         Twzxy:= ((w<>z) AND (x<>y));
         Result:= Twxyz AND (Twyxz AND Twzxy)
       END;
     
     PROCEDURE Enumeration(Np, DateT: Word;
                           VAR L_j: Tab_J; VAR L_t: Tab_T);
       VAR i: Byte;
           a, b, c, d, D10, k, Kmax, La, Lb, Lc, Ld, m, Nmax,
           Ord1, Ord2, Ord3, Ord4, Rng1, Rng2, Rng3, Rng4: Word;
           Tord, Trng: Bool;
       BEGIN
         Kmax:= Np;             IF (Kmax>=Njoueur) THEN Kmax:= Njoueur - 1;
         RandSeed:= 1333000777; D10:= 10 * DateT;  Nmax:= Nj4;
         k:= 0;
         REPEAT
           Inc(k); Aff_Np(k);
           REPEAT
             a:= Random(Nmax); La:= ListeN[a]; Rng1:= La DIV 4;
             Ord1:= La MOD 4;  Inc(Ord1);
             b:= Random(Nmax); Lb:= ListeN[b]; Rng2:= Lb DIV 4;
             Ord2:= Lb MOD 4;  Inc(Ord2);
             c:= Random(Nmax); Lc:= ListeN[c]; Rng3:= Lc DIV 4;
             Ord3:= Lc MOD 4;  Inc(Ord3);
             d:= Random(Nmax); Ld:= ListeN[d]; Rng4:= Ld DIV 4;
             Ord4:= Ld MOD 4;  Inc(Ord4);
             Trng:= Test4E(Rng1, Rng2, Rng3, Rng4);
             Tord:= Test4E(Ord1, Ord2, Ord3, Ord4);
           UNTIL (Trng AND Tord);
           L_t[k][Ord1]:= Rng1;
           Inc(L_j[Rng1].Date, Ord1); L_j[Rng1].OrdJ[Ord1]:= 100 * Ord1;
           L_t[k][Ord2]:= Rng2;
           Inc(L_j[Rng2].Date, Ord2); L_j[Rng2].OrdJ[Ord2]:= 100 * Ord2;
           L_t[k][Ord3]:= Rng3;
           Inc(L_j[Rng3].Date, Ord3); L_j[Rng3].OrdJ[Ord3]:= 100 * Ord3;
           L_t[k][Ord4]:= Rng4;
           Inc(L_j[Rng4].Date, Ord4); L_j[Rng4].OrdJ[Ord4]:= 100 * Ord4;
           Aff_IdJNmax(ListeT[k], Nmax);
           EpurationLn(La, Lb, Lc, Ld, Nmax, ListeN)
         UNTIL (Nmax=0)
       END;
     
     PROCEDURE Init_LstT(VAR L_t: Tab_T);
       VAR i: Byte; k: Word;
       BEGIN
         FOR k:= 0 TO (Njoueur - 1) DO
           FOR i:= 1 TO 4 DO L_t[k][i]:= 0
       END;
     
     PROCEDURE Init_LstJ(VAR L_j: Tab_J);
       VAR i: Byte; k: Word;
       BEGIN
         FOR k:= 0 TO (Njoueur - 1) DO
           BEGIN
             L_j[k].Date:= 0;
             FOR i:= 1 TO 4 DO L_j[k].OrdJ[i]:= i
           END
       END;
     
     PROCEDURE Init_Lst4N(VAR L_n: Tab_4NE);
       VAR k: Word;
       BEGIN
         FOR k:= 0 TO (Nj4 - 1) DO L_n[k]:= k;
         L_n[Nj4]:= 0
       END;
     
     BEGIN
       Init_Lst4N(ListeN); Init_LstJ(ListeJ); Init_LstT(ListeT);
       Enumeration(40, 1, ListeJ, ListeT);
       Controle
     END.

    Je donnerai des précisions sur tout ce qui pourrait présenter d'éventuelles difficultés.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  17. #17
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 160
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 74
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 160
    Points : 2 224
    Points
    2 224
    Billets dans le blog
    9
    Par défaut Rotations pour un tournoi
    Le programme précédent a l'inconvénient de livrer une suite anarchique de combinaisons, dépourvue de toute régularité apparente.
    les possibilités sont sans doute nombreuses, mais les contraintes imposées sont cependant si fortes qu'une part non négligeable des tirages bloque avant finalisation.

    Il existe des solutions très simples, relevant à la limite d'un calcul manuel, et découlant (au niveau des 3 derniers ordres de jeu) du décalage de la liste initiale (0, 1, 2, 3 ... (Njoueur - 1)) de 3 quantités données (DeltaA, DeltaB, DeltaC).

    Le choix d'un triplet approprié permet de s'assurer que chaque joueur n'affronte pas deux fois le même partenaire, et se retrouve associé à 4*3 = 12 joueurs différents au cours des 4 parties successives. Il suffit pour cela d'inspecter chaque ligne de la matrice des joueurs impliqués dans chaque équipe constituée; elle contient, dans le cas le plus favorable, 12 termes égaux à l'unité.

    C'est ce qu'on observe pour le triplet (Δa, Δb, Δc) = (3, 7, 13):

    Nom : Max=1_D=03_07_13.png
Affichages : 93
Taille : 15,3 Ko

    D'autres combinaisons réduisent le nombre de termes non nuls, certains d"entre eux atteignant 2 ou 3 - la somme restant constante et égale à 12: un joueur donné rencontre alors deux ou trois fois le même partenaire.
    Exemples: (Δa, Δb, Δc) = (2, 3, 5) ou (1, 2, 3)

    Nom : Max=2_D=02_03_05.png
Affichages : 88
Taille : 14,3 Ko
    Nom : Max=3_D=01_02_03.png
Affichages : 90
Taille : 15,9 Ko


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  18. #18
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 160
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 74
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 160
    Points : 2 224
    Points
    2 224
    Billets dans le blog
    9
    Par défaut Rotations pour un tournoi
    Le programme source est plus court que le précédent:
    Code Delphi : 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
     PROGRAM Tournoi;
     
     USES Crt, E_Texte;
     
    (*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
     
     Détermination des équipes par décalage des listes de joueurs
     
    HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)
     
     CONST Njoueur = 50; Nj1 = Njoueur - 1; Nj4 = 4 * Njoueur;
           DeltaA = 3;   DeltaB = 6;        DeltaC = 21;
     
     TYPE Tab_4E = ARRAY[1..4] OF Word;
          Joueur = RECORD  Date: Word;
                           OrdJ: Tab_4E  END;
          Tab_T = ARRAY[0..Nj1] OF Tab_4E;
          Tab_J = ARRAY[0..Nj1] OF Joueur;
          Tab_P = ARRAY[0..Nj1, 0..Nj1] OF Byte;
     
     CONST Delta: Tab_4E = (0, DeltaA, DeltaB, DeltaC);
     
     VAR ListeJ: Tab_J;
         ListeT: Tab_T;
         Matrice: Tab_P;
     
     PROCEDURE ControleM(VAR M_a: Tab_P);
       CONST C1 = 40; C2 = C1 + 8; o = 3;
       VAR x: Byte; i, j, k: Word;
       BEGIN
         E(0015); Wt(C2, 4, 'Termes non nuls de la ligne');
         FOR i:= 0 TO Nj1 DO
           BEGIN
             x:= C1;
             FOR j:= 0 TO Nj1 DO
               BEGIN
                 k:= M_a[i, j];
                 IF (k>0) THEN
                   BEGIN
                     IF (k>2) THEN E(0012)
                              ELSE IF (k>1) THEN E(0013)
                                            ELSE E(0011);
                     Inc(x, o); We(x, 6 + i, k, o)
                   END
               END
           END;
         Wt(80, Nj1 + 8, '+'); A_
       END;
     
     PROCEDURE Aff_LstJ;
       CONST C1 = 3; o = 6;
       VAR i: Byte; k: Word;
       BEGIN
         E(1015); Wt(C1, 2, 'DeltaA, DeltaB, DeltaC = ');
         E(0012); FOR i:= 2 TO 4 DO Write(Delta[i]:o);
         E(0015); Wt(C1, 4, 'Rang  Date        Ordre du Jeu');
         FOR k:= 0 TO Nj1 DO
           BEGIN
             E(0012); We(C1, 6 + k, k, 3);
             E(0009); Write(ListeJ[k].Date:o);
             E(0010); FOR i:= 1 TO 4 DO Write(ListeJ[k].OrdJ[i]:o)
           END
       END;
     
     PROCEDURE InitLstJ(VAR L_t: Tab_T; VAR L_j: Tab_J);
       VAR k: Word;
       BEGIN
         FOR k:= 0 TO Nj1 DO
           WITH L_j[k] DO BEGIN
                            Date:= 1; OrdJ:= L_t[k]
                          END
       END;
     
     PROCEDURE Init_Mat(VAR L_t: Tab_T);
       VAR k: Word; Tw: Tab_4E;
       BEGIN
         FOR k:= 0 TO Nj1 DO
           BEGIN
             Tw:= L_t[k];
             Inc(Matrice[Tw[1], Tw[2]]); Inc(Matrice[Tw[2], Tw[1]]);
             Inc(Matrice[Tw[1], Tw[3]]); Inc(Matrice[Tw[3], Tw[1]]);
             Inc(Matrice[Tw[1], Tw[4]]); Inc(Matrice[Tw[4], Tw[1]]);
             Inc(Matrice[Tw[2], Tw[3]]); Inc(Matrice[Tw[3], Tw[2]]);
             Inc(Matrice[Tw[2], Tw[4]]); Inc(Matrice[Tw[4], Tw[2]]);
             Inc(Matrice[Tw[3], Tw[4]]); Inc(Matrice[Tw[4], Tw[3]])
           END
       END;
     
     PROCEDURE Zero_Mat(VAR M_a: Tab_P);
       VAR i, j: Word;
       BEGIN
         FOR i:= 0 TO Nj1 DO
           FOR j:= 0 TO Nj1 DO M_a[i, j]:= 0
       END;
     
     PROCEDURE Init_LstT(VAR L_t: Tab_T);
       VAR i: Byte; j, k: Word;
       BEGIN
         FOR k:= 0 TO Nj1 DO
           FOR i:= 1 TO 4 DO BEGIN
                               j:= k + Delta[i];
                               IF (j>Nj1) THEN Dec(j, Njoueur);
                               L_t[k][i]:= j
                             END
       END;
     
     BEGIN
       Init_LstT(ListeT);                   // Initialisation des 4 listes
       Zero_Mat(Matrice); Init_Mat(ListeT); // Mise à zéro et initialisation de la matrice des joueurs associés   
       InitLstJ(ListeT, ListeJ);            // Initialisation de la liste des joueurs
       Aff_LstJ;          ControleM(Matrice);         // Affichage de la liste des joueurs (ordres de jeu)
     END.                                             // Inventaire et affichage des lignes de la matrice.

    Quoi qu'on en trouve sans difficulté, il serait intéressant de caractériser les triplets (Δa, Δb, Δc) pour lesquels les éléments de la matrice ne dépassent pas l'unité.
    On retrouve plusieurs paires de joueurs dés qu'est vérifiée l'une des relations suivantes:
    Δb = 2.Δa; Δc = 2.Δa; Δc = 2.Δb; Δc = Δa + Δb ;
    d'autres cas peuvent apparaître, impliquant les valeurs complémentaires (Njoueur - Δa, ...etc).

    Petite curiosité: dans le cas de 50 joueurs, le triplet (11,13, 25) donne un seul élément de la matrice égal à 2.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  19. #19
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 160
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 74
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 160
    Points : 2 224
    Points
    2 224
    Billets dans le blog
    9
    Par défaut Rotations pour un tournoi
    Une question basique apparaît, qui n'a pas été envisagée jusqu'à présent: le problème admet-il une (ou plusieurs) solution(s), et de quel type ?
    Si dans la meilleure des répartitions chaque joueur affronte 12 joueurs mutuellement différents au cours de 4 parties successives, cela donne un total de 13 - ce que confirme un autre programme analysant la matrice des rencontres des joueurs, pour toutes les combinaisons possibles (Δa, Δb, Δc).
    Figurent à droite le dernier triplet de l'énumération, et la première ligne (ou colonne) de la matrice:

    Nom : Nj=12_13_Jm=1.png
Affichages : 80
Taille : 8,3 Ko

    Le nombre de solutions augmente ensuite, quoique de manière non régulière:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    Nj= 12    13    14    15    16    17    18    19    20    21    22
    Ns = 0    12     6    44    38   104    76   200   172   364   266
    Dans le cas d'un plus faible nombre de participants, il faut admettre qu'un joueur donné en rencontre un autre plus d'une fois; ainsi lorsque se présentent 12 à 7 joueurs, le nombre minimal de doublets augmente progressivement:

    Nom : Nj=7_8_Jm=2.png
Affichages : 77
Taille : 9,3 Ko
    Nom : Nj=9_10_Jm=2.png
Affichages : 67
Taille : 21,7 Ko
    Nom : Nj=11_Jm=2_Dj=2.png
Affichages : 68
Taille : 7,4 Ko
    Nom : Nj=12_Jm=2_Dj=1.png
Affichages : 64
Taille : 3,8 Ko

    Pour des effectifs plus faibles, les participants sont nécessairement associés par 3 (au moins):

    Nom : Nj=5_6_Jm=3.png
Affichages : 65
Taille : 4,4 Ko


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  20. #20
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 160
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 74
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 160
    Points : 2 224
    Points
    2 224
    Billets dans le blog
    9
    Par défaut
    @ Winjerome
    Merci pour l'initiative de coloration syntaxique !
    Dernière modification par Winjerome ; 24/09/2020 à 21h11. Motif: Coloration syntaxique [ CODE=Delphi] … [/CODE]
    Je ne connaissais pas cette commande, et la présentation s'en trouve grandement améliorée.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

Discussions similaires

  1. Calcul de rotation pour faire correspondre deux modules
    Par noals dans le forum Algorithmes et structures de données
    Réponses: 19
    Dernier message: 12/05/2016, 08h49
  2. Comment générer une matrice de rotation pour un axe et un angle donnés ?
    Par Kromagg dans le forum Développement 2D, 3D et Jeux
    Réponses: 6
    Dernier message: 20/07/2009, 13h45
  3. Compilation pour préparation tournoi mondial ..
    Par Aurore.boreale dans le forum Débuter
    Réponses: 6
    Dernier message: 27/01/2009, 22h07
  4. Tirage au sort pour un tournoi de belote
    Par aldom dans le forum VB.NET
    Réponses: 1
    Dernier message: 24/06/2007, 21h43
  5. Définir un angle de rotation pour une image
    Par mateo.14 dans le forum C++
    Réponses: 5
    Dernier message: 25/03/2005, 15h43

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo