Composition de match

Merci pour ton analyse qui me parais bien et productive.
Après, si tout le monde ne joue pas avec tout le monde, est ce
problèmatique ? Je serais enclin à penser que oui, mais si on ne peut
pas faire autrement....
Par contre, il faut juste respecter un impératif : chaque semaine, TOUS
les joueurs doivent jouer

J'en suis à 3 tubes de dolipran :p


HB avait prétendu :

Bonjour,

le pb est compliqué donc le message est long ... désolé ;o)


concernant le calcul de Lsteph :
=============================== > Un match est une paire de paires...

{ {A ; B} ; {C ; D} }


L'utilisation des accolades signale
que ces structures ne sont pas ordonnées.

Puisqu'il y a 24 joueurs ,

le nb de groupes {A ; B; C ; D} distincts

est COMBIN(24;4) = 24*23*22*21/(4*3*2*1)

ce qui fait tout de même 10 626 ...


Ensuite, chaque groupe {A ; B ; C ; D}
de 4 éléments peut être partagés
de 3 façons : AB et CD ; AC et BD ; AD et BC

Cela fait donc en tout 31 878 matchs distincts

C'est bien moins que la valeur annoncée par Lsteph
et bien plus que les 138 annoncés par JLuc69

MAIS

on voit bien sur les 3 maths ci-dessus
que A jouera 2 fois contre chaque joueur.

et plus généralement, ces 31 878 matchs distincts
ne fournissent pas une liste optimale !!!

Concernant le classeur (mis sur ci-joint.com)
=========================================== >
Il suppose que chaque paire n'aura pas à jouer plusieurs fois
d'où le nb de 276 ... mais ce nombre est-il bon ? ...

Début d'analyse
================ >
Imaginons les matchs avec A :
Avec 11 matchs il joue
avec 11 différents ( B à L)
et contre tous sauf B

AB CD
AC EF
AD GH
AE IJ
AF KL
AG MN
AH OP
AI QR
AJ ST
AK UV
AL WX

Il faut donc que A fasse encore des matchs avec M à X pendant que les autres
remplissent partiellement leurs obligations ;o)

B et M à X n'ont fait qu'un match, C à L en ont déjà fait deux ...
complétons les maths de A pour équilibrer

AM BX
AN DE
AO FG
AP HI
AQ JK
AR LM
AS VW
AT PQ
AU RS
AV TU
AW NO
AX BC

ainsi, avec 23 matchs :
- A a joué avec tous
- A a joué contre tous


Passons à B qui a déjà fait trois matchs :
BX AM
BC AX
AB CD


Il doit donc encore jouer
avec D à W et
AU MOINS contre E à W sauf M :


BD EF
BE GH
BF IJ
BG KL
BH NO
BI PQ
BJ RS
BK TU
BL VW

BM UV
BN WX
BO GH
BP IJ
BQ KL
QR MN
BS OP
BT QR
BU ST
BV CD
BW EF

Avec ces 20 matchs supp :

B a fait tous les matchs obligatoires

on en est à 23+20 = 43 matchs

... bref on le voit bien, ...
on va pouvoir respecter les contraintes
avec un nombre de matchs très limité
mais il faudrait mieux choisir les secondes équipes
(là j'ai pris assez bêtement)

Par exemple :

les 4 matchs déjà faits par C :
CD AB
AC EF
CD BV
BC AX

il a joué deux fois avec D

les 5 matchs déjà faits par D :
CD AB
AD GH
DE AN
BD EF
CD BV
il a joué deux fois avec C

les 4 matchs déjà faits par X :
AL WX
AM BX
AX BC
BN WX

il a joué deux fois avec W


les 6 matchs déjà faits par W :
WX AL
VW AS
AW NO
VW BL
WX BN
BW EF

il a joué deux fois avec X et deux fois avec V ...

GASP !!!! c'est la panique ...

Peut-on modifier une des listes du dessus
pour éviter ces problèmes ?...

peut-être ...


Les outils "théoriques" pour déterminer proprement
une liste optimale de matchs
sont, je pense, assez compliqués ...
je ne vois rien d'évident pour l'instant.

Une grosse macro brutale
peut probablement proposer qqchose rapidement
MAIS
faire tourner qqchose (VBA) qui fournira
une _solution optimale_
ne me semble pas immédiat ...

... et encore, je n'évoque pas les problèmes
de disponibilité des courts ...

Bref ... je ne vois aucun argument simple permettant
de proposer une liste optimale de matchs ...
( sachant qu'à la main c'est pas évident)

Il me semble que ce problème
est plus proche d'un pb de maths (combinatoire)
(concours d'entrée à Normale-sup ou à HEC)
que d'un problème de VBA ;o)


Pour finir :

Pour commencer, il faudrait reprendre le problème
en faisant des listes à la main
pour 4 joueurs, 5 joueurs, 6 joueurs, ...
De fécondes idées peuvent surgir
de l'observation
- des résultats
- de la méthode adoptée


Cordialement,

HB





Le 29/07/2016 à 14:07, JLuc69 a écrit :

Dans le fichier joint, je pense avoir mis toutes les équipes possible,
soit 276 si je n'ai pas fait de gourance :p


LSteph a formulé la demande :

Bonjour,

Ca peut faire bien plus il me semble....sauf erreur
Le joueur24 a 23 partenaires possibles
il en reste 22 le 22 en a 21
le 20 en 19 ...
...
.. le 2 en a 1
Soit possibilités de constitution d'équipes 23*21*19*17*15*13*11*..*1

Bon courage si je ne me trompe pas.

Cordialement.

--
LSteph




Le jeudi 28 juillet 2016 16:45:46 UTC+2, JLuc69 a écrit :

Salut le groupe,

Je me retrouve avec un petit problème posé par un ami que mes
quelques neuronnes n'arrivent pas à gérer.
Les données du problème :
- Ils sont 24 joueurs (de tennis, ça ne sert pas, mais ce sera peut
être plus parlant :p)
- Ils ont 6 cours de disponnible par semaine dont 3 le mardi et 3 le
jeudi
- Ils voudraient pouvoir jouer avec tout le monde et rencontrer tout
le monde sur l'année

J'ai fais des calculs, ça ferait 276 doubles différent donc 138
matchs possibles. Sur 48 semaines, ils ont la possibilité de faire
48*6(8 matchs. Ce qui fait qu'ils pourraient faire fois la liste
trouvée, plus 12 rencontres aléatoires.
J'ai commencer un fichier excel où j'ai tous les binomes mais je
coince sur les rencontres pour que chaque semaine, tout le monde joue
et que sur la liste des rencontres, tout le monde joue avec tout le
monde et rencontre tout le monde.

C'est le coté ardu de la tâche (au moins pour moi). Pourriez vous
m'aider à établir cette liste ?
Je vous mets ce que j'ai déjà commencer :
http://www.cjoint.com/c/FGCoSYhVFug

Un grand merci si vous pouvez me donner des pistes pour y arriver

JLuc

---
L'absence de virus dans ce courrier électronique a été vérifiée par le
logiciel antivirus Avast.
https://www.avast.com/antivirus

reste plus qu'à apporter un sac et 24 billes pour le tirage au sort ;-)
isabelle

Le 2016-07-29 à 11:51, JièL a écrit :

Ce qui m'amuse, c'est que ce casse tête ne tient pas compte des gens absents,
ceux qui changent de date, ceux qui se trompent de semaine, des vacances etc etc
et qui va faire que de toute façon ça sera un joyeux bord*** ;-)))))

Bon courage quand même :-)

j'ai suivi mon conseil ;o)

tests.xls est là :
http://www.cjoint.com/c/FGDvXoBxk6C

J'ai établi des listes pour les cas 4 à 7 joueurs

1) En ce qui concerne la contrainte de calendrier
il me semble que
si on trouve "le moins de matchs possibles"
ce sera d'autant plus facile à mettre en place ;o)

il faut savoir comment générer la liste des matchs
pour ensuite utiliser cette liste ...
(avançons pas à pas)

2) Il semble qu'effectivement
on peut utiliser
les 24*(24 - 1) / 2 paires
en les associant 2 par deux
pour que, en plus, chacun joue contre tous.

(Cela ne me semble pas si évident ... mais bon)

Cela fera donc effectivement 138 matchs nécessaires.

Mais attention, toutes les combinaisons
ne vont pas forcément convenir...

3) Il faut donc d'abord trouver un algo efficace
qui fournit une liste convenable de 138 matchs.

On devrait pouvoir faire en sorte que
- chacun joue AVEC chacun (une fois)
- chacun affronte exactement deux fois chacun
(comme dans les cas n=4 et n=5)
Cet équilibre parfait sera fort utile pour la suite :
Répartir tout ça dans le calendrier ...
(mais ce sera sans doute plus facile ...)

HB



---
L'absence de virus dans ce courrier électronique a été vérifiée par le logiciel antivirus Avast.
https://www.avast.com/antivirus

bonjour JLuc,

j'ai fais une approche différente, approche dont tu avais parlé mais à ton dire
que tu avais abandonné,
mais peut être que ... la solution aléatoire n'est pas encore exclue,

http://www.cjoint.com/c/FGEfbz5h7ia

Sub Tableau_aleatoire_sans_doublon()
'Déclare un tableau pour 24 joueurs, (6 courts pour chacun 4 joueurs)
Dim Tableau(1 To 4, 1 To 6) As String
'Déclare un tableau à 1 dimensions pour 24 joueurs.
Dim joueur(1 To 24) As String
Dim i As Integer, j As Integer, x As Integer, n As Integer, Nb As Integer
Dim k As Single, S As String, Resultat As String

Randomize
n = 24 'maximum : 32735
For Nb = 1 To n
S = S & ChrW(32 + Nb)
Next

'liste aléatoir des joueurs sans doublon
Do
Nb = Int(Rnd * Len(S) + 1)
k = k + 1
joueur(k) = AscW(Mid(S, Nb, 1)) - 32
S = Left$(S, Nb - 1) & Mid$(S, Nb + 1)
Loop Until S = ""

'inscrit la liste aléatoire dans le tableau
For i = 1 To UBound(Tableau, 2)
For j = 1 To UBound(Tableau, 1)
x = x + 1
Tableau(j, i) = joueur(x)
Next j
Next i

'Affiche le résultat sur l'onglet "Feuil1"
Sheets("Feuil1").Range("A2").Resize(UBound(Tableau, 2), 4) =
Application.Transpose(Tableau)
End Sub

isabelle

Le 2016-07-29 à 12:41, JLuc69 a écrit :

Merci pour ton analyse qui me parais bien et productive.
Après, si tout le monde ne joue pas avec tout le monde, est ce problèmatique ?
Je serais enclin à penser que oui, mais si on ne peut pas faire autrement....
Par contre, il faut juste respecter un impératif : chaque semaine, TOUS les
joueurs doivent jouer

...tu as dit "avec tout le monde" mais sinon j'ai une solution "Contre chaq ue":

Pour chaque équipe Prénom1 Prénom2
Puis un tableau des (paires) Equipes en Abcisse et transposées en ordo nnées
Tu remplis les numéros des matchs
en n'inscrivant rien dans ni sous la diagonale (équipes identiques)
Donc je ne comprends pas la théorie d HB qui ne comprenais pas la mien ne.

Cela fera 66 matchs et tout le monde aura rencontré chaque joueur.
donc 11 semaines avec 6 courts.

12 équipes si tu en mets une sur un terrain il en reste 11 pour venir en face
12*11=132 soit 2 équipes par matchs 132/2=66 matchs
http://www.cjoint.com/c/FGEiaIaOsMw


Après siv en plus chacun doit avoir eu tous les partenaires, tu peux p ermuter chaque joueur en décalant à chaque fois pour qu'ils aient joué avec chaque ce qui fait 23 permutations , on arrive déjà   à 1518 matchs. Tu n'auras pas assez de courts!

Cordialement.

--
LSteph

... je me réponds à moi même.
Il faudra en fait au moins une permutation de joueur (cf. mon petit tableau ) pour que chacun ait joué aussi contre son partenaire cela fait donc le double de matchs soit 132.
On peut imaginer une distribution aléatoire des joueurs dans la liste puis,
Première session joueur1 avec joueur 2
Seconde session joueur 1 avec joueur 3.

...

Le samedi 30 juillet 2016 10:01:26 UTC+2, LSteph a écrit :

...tu as dit "avec tout le monde" mais sinon j'ai une solution "Contre ch aque":

Pour chaque équipe Prénom1 Prénom2
Puis un tableau des (paires) Equipes en Abcisse et transposées en or données
Tu remplis les numéros des matchs
en n'inscrivant rien dans ni sous la diagonale (équipes identiques)
Donc je ne comprends pas la théorie d HB qui ne comprenais pas la mi enne.

Cela fera 66 matchs et tout le monde aura rencontré chaque joueur.
donc 11 semaines avec 6 courts.

12 équipes si tu en mets une sur un terrain il en reste 11 pour veni r en face
12*11=132 soit 2 équipes par matchs 132/2=66 matchs
http://www.cjoint.com/c/FGEiaIaOsMw


Après siv en plus chacun doit avoir eu tous les partenaires, tu peux permuter chaque joueur en décalant à chaque fois pour qu'ils aie nt joué avec chaque ce qui fait 23 permutations , on arrive déj à à 1518 matchs. Tu n'auras pas assez de courts!

Cordialement.

--
LSteph

Je m'aperçois que le problème est beaucoup plus épineux que je ne
l'avais envisagé au départ...

...
http://www.cjoint.com/c/FGEi0Wljd8w

Bonjour JLuc

tel qu'énoncé, c'est infaisable.
Si chaque joueur doit faire équipe avec chacun des 23 autres, pour jouer une
fois contre chacun des 22 autres, cela fera 11 rencontres, rien qu'avec les
joueurs A+B.
11 autres avec A+C .... . Tout cela rien que pour le joueur A
Idem pour B, avec 11 rencontres en moins (celles déjà jouées avec A).

Si, en plus, tu veux de l'aléatoire .....



Jacques
" Le vin est au repas ce que le parfum est à la femme."
.
"JLuc69" a écrit dans le message de groupe de discussion :
mn.f2717e07b55662be.126037@free.fr...

Je m'aperçois que le problème est beaucoup plus épineux que je ne
l'avais envisagé au départ...


---
L'absence de virus dans ce courrier électronique a été vérifiée par le logiciel antivirus Avast.
https://www.avast.com/antivirus

Non, il y a méprise
Je n'ai pas dit que chaque joueur devait jouer avec chaque autre contre
tous les autres joueurs, mais que chaque joueur devait pouvoir jouer
aves les 23 autres et si possible contre tous les autres mais quelle
que soit la compsition des adversaire.

Dans la théorie, le joueur N°1 pourra composer 23 duos, donc il fera 23
parties qui s'étaleront sur 23 semaines (1 partie par semaine). Sur ces
23 parties, il serait bien qu'il recontre les 23 autres quelque soit la
composition de l'équipe adverse.
Une fois cette liste composée, ils la répeteront pour avoir des matchs
sur 46 semaines. Pour les 2 semaines restantes, ils pourraient soit
faire un tirage aléatoire comme le propose Isabèle, soit reprendre
quelqus matchs de la première liste


Dans son message précédent, Jacquouille a écrit :

Bonjour JLuc

tel qu'énoncé, c'est infaisable.
Si chaque joueur doit faire équipe avec chacun des 23 autres, pour jouer une
fois contre chacun des 22 autres, cela fera 11 rencontres, rien qu'avec les
joueurs A+B.
11 autres avec A+C .... . Tout cela rien que pour le joueur A
Idem pour B, avec 11 rencontres en moins (celles déjà jouées avec A).

Si, en plus, tu veux de l'aléatoire .....



Jacques
" Le vin est au repas ce que le parfum est à la femme."
.
"JLuc69" a écrit dans le message de groupe de discussion :
mn.f2717e07b55662be.126037@free.fr...

Je m'aperçois que le problème est beaucoup plus épineux que je ne
l'avais envisagé au départ...


---
L'absence de virus dans ce courrier électronique a été vérifiée par le
logiciel antivirus Avast.
https://www.avast.com/antivirus