Petit casse-tête PHP...

[garbage06]

Bonjour,

Je me tire un peu les cheveux à trouver "la bonne boucle" afin de résoudre ce petit problème :

Pour un jeu de type Championnat, j'ai besoin de créer, avant le début de la compétition, la liste de tous les matchs qui auront lieu.

Par exemple pour une poule de 4 joueurs (J1, J2, J3 et J4), il y aura 3 journées de championnat :

1ère journée :

J1 contre J2

J3 contre J4

2ème journée :

J1 contre J3

J2 contre J4

3ème journée :

J1 contre J4

J2 contre J3

Je cherche donc une méthode "optimisée" pour réalisée ceci car mon script PHP devra créer l'ensemble des matchs pour 16 poules de 25 joueurs.

J'ai fait plusieurs tentatives infructueuses (+ de 30 secondes en exécution).

Merci par avance si ce problème vous inspire.

Franck

[Bourinho]

Salut,

je crois que je viens de trouver une solution... pour un nombre d'équipe paire!

En fait, ma méthode consiste à faire un tableau... je vais prendre l'exemple avec 8 équipes :

Les nombres qui apparaitront dans le tableau correspondent au numéro de la journée à laquelle aura lieu le match.

X12345678

1X

2XX

3XXX

4XXXX

5XXXXX

6XXXXXX

7XXXXXXX

8XXXXXXXX

On remplit chaque colonne sauf la dernière comme suit (pour les colonnes de 2 à 7):

On commence par la première ligne en y mettant comme nombre celui qui est au-dessus (c'est à dire le numéro de l'équipe qui jouera contre l'équipe numéro 1) moins 1. Ensuite, pour remplir cette colonne, on incrémente jusqu'à 7 en descendant... et on recommence à 1 pour poursuivre si nécessaire.

Pour la dernière colonne (la colonne 8 dans notre exemple):

On commence aussi de la même manière (c'est à dire que l'on met 8-1=7 à la première ligne) mais on poursuit par les nombres paires 2, 4, 6, ... et ensuite les nombres impaires 1, 3, 5...

Pour notre exemple, ça donne :

X 1 2 3 4 5 6 7 8

1 X 1 2 3 4 5 6 7

2 X X 3 4 5 6 7 2

3 X X X 5 6 7 1 4

4 X X X X 7 1 2 6

5 X X X X X 2 3 1

6 X X X X X X 4 3

7 X X X X X X X 5

8 X X X X X X X X

Avec cette méthode, ça ne devrait pas demander 30s pour générer un championnat

En effet, pour N équipes, le tableau T est défini par :

pour 0<i<j<N, T(i,j) = (i+j)-2 modulo (N-1)

pour 0<i<N, T(i,N) = 2(i-1) modulo (N-1)

tel que pour tout i et pour tout j, 0<T(i,j)<N...

Après, si tu veux faire des matchs aller-retour, tu peux poser, pour 0<i<j<N+1 :

T(j,i) = 2N-1-T(i,j)

T(j,i) = N-1+T(i,j)...

Voilà, A+

Modifié 9 Novembre 2006 par Bourinho