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
    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

    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
    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

    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
    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
    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
    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
    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
    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é
    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
    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é
    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
    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
    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 éclairé
    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)

###raw>template_hook.ano_emploi###