Discussion :

[4910Lab]

Bonjour à tous.

J'ai une demande un peu spéciale et je ne trouve pas ce qui pourrait convenir. Mon algorithmique est un peu rouillée pour ce genre d'exercice, donc je m'adresse à Vous.

J'ai une demande pour un tournoi de pétanque Pro-Am.

Pour ceux qui comme moi ne connaissent pas le concept de Pro-Am, ce sont X professionnels de la pétanque qui vont jouer avec X amateurs un tournoi. Pour que les parties soient équilibrées, chaque équipe change à chaque tour. Et afin que ce soit équilibré d'avantage, les adversaires changent à chaque fois.

En exemple, si on a X=8 équipes, le premier tour donnera les matches suivants :

A	1	-	B	2
C	3	-	D	4
E	5	-	F	6
G	7	-	H	8

Ça, c'est la partie la plus simple.

Ensuite, il faut mixer les équipes, le tout afin de réaliser 7 tours pour que ça marche correctement. Je suis conscient que 8 équipes totalement différentes à chaque tour n'est pas possible, il y a un moment ou 2 pros finiront par se retrouver. Il faut juste éviter qu'ils ne se retrouvent plus qu'une fois.

J'avais imaginé générer tous les tours possibles, puis essayer toutes les possibilités avec des scores pour essayer de trouver celle avec le moins élevé.

Ma fonction qui compare les tours aux précédents fonctionne, et donne un score correct, mais je n'arrive pas à faire les générations des équipes.

Tour 1 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8
Tour 2 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 1
Tour 3 A 3 B 4 C 5 D 6 E 7 F 8 G 1 H 2
Tour 4 A 4 B 5 C 6 D 7 E 8 F 1 G 2 H 3
Tour 5 A 5 B 6 C 7 D 8 E 1 F 2 G 3 H 4
Tour 6 A 6 B 7 C 8 D 1 E 2 F 3 G 4 H 5
Tour 7 A 7 B 8 C 1 D 2 E 3 F 4 G 5 H 6
Tour 8 A 8 B 1 C 2 D 3 E 4 F 5 G 6 H 7
J'ai une fonction de base qui génère les tours de base. Mais il existe encore plein d'autres combinaisons.

J'aurais donc besoin de votre aide pour cela.

J'ai donc X lettres pour les Pros.
J'ai les chiffres de 1 à X pour les Am.

J'espère que vous avez compris.

Je vous remercie d'avance.

Claude

[ProgElecT]

Salut, bienvenue sur DVP

Je pense que ta question serait mieux dans le Forum ==> Général Développement ==> Algorithme & Mathématiques ==> Algorithmes et structures de données
Suite aux réponses, tu pourras revenir dans le forum php pour mettre la formule en place avec la bonne syntaxe php.

[Séb.]

Je n'ai pas compris ce que tu arrives déjà à faire et ce que tu n'arrives pas à faire.

Donne-nous un exemple de données en entrée, de données en sortie, et de l'état de ton avancement

Fais un exemple avec X = 4, ça devrait être suffisant pour le principe.

[4910Lab]

@ProgElecT => Possible, effectivement, c'est de l'algo générale quelque part. Je vais essayer de le poster là.
@Séb. => Si je hardcode mes matches qui vont bien, j'arrive à déterminer si j'ai des doublons quelque part.

J'ai un tableau ressemblant à

Code :

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

1
2
3
4
5
6
7
8
9
10
11
//Tour 1 - Match 1
    $matches[1][1][1]["pro"]="A";
    $matches[1][1][1]["am"]=1;
    $matches[1][1][2]["pro"]="B";
    $matches[1][1][2]["am"]=2;
 
    //Tour 1 - Match 2
    $matches[1][2][1]["pro"]="C";
    $matches[1][2][1]["am"]=3;
    $matches[1][2][2]["pro"]="D";
    $matches[1][2][2]["am"]=4;

Et quand je passe ça à la moulinette pour vérifier mes critères, j'ai

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
/var/www/carto/equipes.php:191:
array (size=32)
  0 => string 'A2' (length=2)
  1 => string 'B1' (length=2)
  2 => string 'C4' (length=2)
  3 => string 'D3' (length=2)
  4 => string 'E6' (length=2)
 [...]
/var/www/carto/equipes.php:192:
array (size=6)
  0 => string 'D3' (length=2)
  1 => string 'H7' (length=2)
  2 => string 'F4' (length=2)
  3 => string 'B8' (length=2)
  4 => string 'H6' (length=2)
  5 => string 'D2' (length=2)
SCORE : 600

Le score de 600 m'indique que j'ai 6 doublons qui sont visibles juste au dessus.

---

Au final, ce que je n'arrive pas à faire, c'est générer toutes les tours possibles.

À chaque tour, j'ai un AM lié à un PRO, donc j'ai par exemple A1 B2 C3 D4 au premier tour, puis A2 B3 C4 D1 au tour 2, etc. Là j'ai juste fait un décalage, mais ça pourrait être A3 B1 C4 D2.

Une fois que les tous les tours possibles sont tirés, il faut que j'essaye d'associer les matches.

Les matches peuvent être A1 contre B2 et C3 contre D4 au premier tour par exemple. Puis B4 contre D1 et A2 contre C3 au 2ème tour.

Une fois qu'ils sont générés, je sais les vérifier avec la partie qui fonctionne déjà.

[mathieu]

avec 8 équipes, il y a 8! = 40 320 façons d'organiser les équipes.
mais ensuite si vous ne voulez pas qu'une équipe (pro ou am) ne croisent pas 2 fois les mêmes équipes adverses, vous ne pouvez faire que 7 tours.

comme disait Séb., essayez de faire des essais avec un nombre plus petit, par exemple 4.
si par exemple vous faites les associations A1 B2 C3 D4 et qu'on regarde les tours adversaires de A1. on aura alors un tour contre B2 puis C3 puis D4.
et quelques soientt les combinaisons, l'équipe amateur 1 sera contre .2 puis .3 puis .4 et une 4e rencontre fera forcement un doublon.

donc pour 8 équipes, il ne peut y avoir que 7 tours et un 8e tour fera forcement un doublon.

[4910Lab]

@Mathieu => Le problème sont les équipes mixées. Chaque pro joue avec chaque Am contre un autre pro et un autre am à chaque tour.

Logiquement, même le 7ème tour reprend déjà un doublon au niveau des pros.

Il faut donc que j'arrive à générer les 8! possibilités. Puis, que je les assemble en matches, et ensuite que j'élimine les doublons.

Et il y a plusieurs types de doublons, sinon c'est pas drôle. Un pro contre un pro, un am contre un am, et un am contre un pro (sinon les am en ont marre s'ils tombent plusieurs fois de suite sur le même pro)

[mathieu]

Logiquement, même le 7ème tour reprend déjà un doublon au niveau des pros.

je n'ai pas compris, si on reprend les 4 équipes, on a
A1 contre B2
A1 contre C3
A1 contre D4
B2 contre C3
B2 contre D4
C3 contre D4

donc avec 4 équipes, chaque groupe joue 3 fois contre chacun des 3 autres groupes.
ce n'est pas ce que vous recherchez ?

[Séb.]

Si on reprend la matrice exemple du 1er message, on voit que chaque amateur aura joué 1 fois avec chaque pro à l'issue des 8 tours.
Il y a un décalage des joueurs amateurs => Au tour suivant l'amateur joue avec le pro contre qui il était au tour précédent.
Par contre les joueurs pro jouent toujours contre les mêmes joueurs pro au long des 8 tours.
Est-ce ce que tu veux ? Si non donne un exemple.

[4910Lab]

@Seb. Ce n'est pas tout à fait ce que je veux, il faut aussi que les pros s'amusent, donc ils doivent jouer les uns contre les autres aussi. C'est là que ça devient tendu.

J'ai le tirage parfait à 16 équipes, mais à 8 je n'arrive pas à trouver un tirage correct (pas parfait, c'est pas possible)

À 16 voilà mon tirage parfait au format Excel. Les colonnes P à U sont les vérifications de doublons. Si un doublon est présent, il se met en rouge.

Trophée des As 2023-2.xlsx

@Mathieu

Si on a 4 équipes, au premier tour on devrait avoir

A1 - B2
C3 - D4

Ensuite on change les équipes

A2 - C1
B4 - D3

Puis au 3ème tour on coince

A3 - D4 pas possible D4 déjà présent T1
A3 - D2 pas possible 2 a déjà joué contre A au T1
A4 - D1 pas possible 1 a joué contre A au T2
etc...

:'(

[Toufik83]

Bonjour,

Pour répondre au premier message, voilà un bout de code (que vous pouvez développer ...) qui permet de générer 8 groupes différents chacun contient 8 tours :

Code php :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<?php 
$pros=range('A','H');$ama=range(1,8);
$tours=array_map(function($value,$index)use($ama,$pros){
	$newPros=$newPros??$pros;
	$newPros=array_merge(array_splice($newPros,$index),$newPros);
	return array_map(function($number)use($ama,$newPros){
		$newAma=$newAma??$ama;
		$newAma=array_merge(array_splice($newAma, $number),$newAma);
		return implode(" ",array_map(function($a,$b){return $a.$b;},$newPros,$newAma));		
	},range(0,7));
},$pros,array_keys($pros));
 
echo "<pre>";
print_r($tours);
echo "</pre>";

Résultat :

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
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
Array
(
    [0] => Array
        (
            [0] => A1 B2 C3 D4 E5 F6 G7 H8
            [1] => A2 B3 C4 D5 E6 F7 G8 H1
            [2] => A3 B4 C5 D6 E7 F8 G1 H2
            [3] => A4 B5 C6 D7 E8 F1 G2 H3
            [4] => A5 B6 C7 D8 E1 F2 G3 H4
            [5] => A6 B7 C8 D1 E2 F3 G4 H5
            [6] => A7 B8 C1 D2 E3 F4 G5 H6
            [7] => A8 B1 C2 D3 E4 F5 G6 H7
        )
 
    [1] => Array
        (
            [0] => B1 C2 D3 E4 F5 G6 H7 A8
            [1] => B2 C3 D4 E5 F6 G7 H8 A1
            [2] => B3 C4 D5 E6 F7 G8 H1 A2
            [3] => B4 C5 D6 E7 F8 G1 H2 A3
            [4] => B5 C6 D7 E8 F1 G2 H3 A4
            [5] => B6 C7 D8 E1 F2 G3 H4 A5
            [6] => B7 C8 D1 E2 F3 G4 H5 A6
            [7] => B8 C1 D2 E3 F4 G5 H6 A7
        )
 
    [2] => Array
        (
            [0] => C1 D2 E3 F4 G5 H6 A7 B8
            [1] => C2 D3 E4 F5 G6 H7 A8 B1
            [2] => C3 D4 E5 F6 G7 H8 A1 B2
            [3] => C4 D5 E6 F7 G8 H1 A2 B3
            [4] => C5 D6 E7 F8 G1 H2 A3 B4
            [5] => C6 D7 E8 F1 G2 H3 A4 B5
            [6] => C7 D8 E1 F2 G3 H4 A5 B6
            [7] => C8 D1 E2 F3 G4 H5 A6 B7
        )
 
    [3] => Array
        (
            [0] => D1 E2 F3 G4 H5 A6 B7 C8
            [1] => D2 E3 F4 G5 H6 A7 B8 C1
            [2] => D3 E4 F5 G6 H7 A8 B1 C2
            [3] => D4 E5 F6 G7 H8 A1 B2 C3
            [4] => D5 E6 F7 G8 H1 A2 B3 C4
            [5] => D6 E7 F8 G1 H2 A3 B4 C5
            [6] => D7 E8 F1 G2 H3 A4 B5 C6
            [7] => D8 E1 F2 G3 H4 A5 B6 C7
        )
 
    [4] => Array
        (
            [0] => E1 F2 G3 H4 A5 B6 C7 D8
            [1] => E2 F3 G4 H5 A6 B7 C8 D1
            [2] => E3 F4 G5 H6 A7 B8 C1 D2
            [3] => E4 F5 G6 H7 A8 B1 C2 D3
            [4] => E5 F6 G7 H8 A1 B2 C3 D4
            [5] => E6 F7 G8 H1 A2 B3 C4 D5
            [6] => E7 F8 G1 H2 A3 B4 C5 D6
            [7] => E8 F1 G2 H3 A4 B5 C6 D7
        )
 
    [5] => Array
        (
            [0] => F1 G2 H3 A4 B5 C6 D7 E8
            [1] => F2 G3 H4 A5 B6 C7 D8 E1
            [2] => F3 G4 H5 A6 B7 C8 D1 E2
            [3] => F4 G5 H6 A7 B8 C1 D2 E3
            [4] => F5 G6 H7 A8 B1 C2 D3 E4
            [5] => F6 G7 H8 A1 B2 C3 D4 E5
            [6] => F7 G8 H1 A2 B3 C4 D5 E6
            [7] => F8 G1 H2 A3 B4 C5 D6 E7
        )
 
    [6] => Array
        (
            [0] => G1 H2 A3 B4 C5 D6 E7 F8
            [1] => G2 H3 A4 B5 C6 D7 E8 F1
            [2] => G3 H4 A5 B6 C7 D8 E1 F2
            [3] => G4 H5 A6 B7 C8 D1 E2 F3
            [4] => G5 H6 A7 B8 C1 D2 E3 F4
            [5] => G6 H7 A8 B1 C2 D3 E4 F5
            [6] => G7 H8 A1 B2 C3 D4 E5 F6
            [7] => G8 H1 A2 B3 C4 D5 E6 F7
        )
 
    [7] => Array
        (
            [0] => H1 A2 B3 C4 D5 E6 F7 G8
            [1] => H2 A3 B4 C5 D6 E7 F8 G1
            [2] => H3 A4 B5 C6 D7 E8 F1 G2
            [3] => H4 A5 B6 C7 D8 E1 F2 G3
            [4] => H5 A6 B7 C8 D1 E2 F3 G4
            [5] => H6 A7 B8 C1 D2 E3 F4 G5
            [6] => H7 A8 B1 C2 D3 E4 F5 G6
            [7] => H8 A1 B2 C3 D4 E5 F6 G7
        )
 
)

Sinon si vous voulez utiliser les indexes "pro" et "am", remplacez implode(" ",array_map(function($a,$b){return $a.$b;},$newPros,$newAma)); par array_map(function($a,$b){return ["pro"=>$a,"am"=>$b];},$newPros,$newAma);