Bonjour,
Je savais pas trop quel titre mettre sur mon sujet alors je vais tenter d'expliquer plus en détail.
Cela ressemble en partie à un sujet plus bas sur ce forum, mais pas totalement: https://www.developpez.net/forums/d2...tions-tournoi/
Imaginez un groupe de personnes: N
Toutes ses personnes sont répartis dans des groupes de k personnes. (naturellement, N doit être divisible entier par k)
c'est la 1ere itération.
Mon but, c'est de refaire autant de répartition que possible pour que chaque personnes soit avec des personnes qu'il ne connait pas dans chaque nouveau groupe.
J'aimerais savoir le nombre d'itération maximum que l'on peut faire pour N et k donné. Et aussi s'il existait un algorithme permettant de répartir les différentes personnes sans répétition.
Si je prend un exemple facile: 9 personnes dans des groupes de 3: on trouve 4 itérations.
1= (A1, A2, A3), (B1, B2, B3), (C1, C2, C3)
2= (A1, B1, C1), (A2, B2, C2), (A3, B3, C3)
3= (A1, B2, C3), (A2, B3, C1), (A3, B1, C2)
4= (A1, B3, C2), (A2, B1, C3), (A3, B2, C1)
(j'utilise Ax,Bx,Cx car c'est plus facile a voir visuellement mais dans mon code, ce sont des nombres).
Quelques remarques:
Si k*k < N alors une seule itération est possible.
Si k*k = N, alors en théorie, il y a (N - 1) / (k - 1) itérations possible (ou plus simple k + 1): j'ai pu le verifier pour k < 6. (k3 = 4, k4 = 5, k5 = 6
Si k*k > N, là, je n'ai aucune idée s'il y a une équation (mon programme me trouve n12 et k3= 3, n15 et k3= 5) ET ce n'Est pas possible
Si N=k², et k est un nombre premier, sur papier j'arrive à avoir un algorithme pour générer toutes les itérations. En faisant des rotations par colonne dans une matrice.
Si N=k², et k est pas un nombre premier, à partir de k=6, ca devient compliqué de trouver quelque chose.
Cela fait 3 semaines que je réfléchi a ce problème.
J'ai un programme (en c#) qui fait de quoi mais il n'est pas suffisament intelligent... tout ce qu'il fait, c'est prendre le 1er élément disponible dans une liste et fait du recursive avec un algorithme de backtrack.. mais que pour la création d'une itération a la fois.
Le problème, avec k=5 et =25, le programme ne trouve que 2 itérations car prioriser le 1er élément n'est pas l'algo à utiliser pour maximiser le nombre d'itérations.
Et si k²<N, mon programme est en loop infinie avec de trop gros nombres (mais j'arrive pas a trouver d'ou cela provient)
Pour limiter le problème, je cherche avec des valeurs max de N=42 et k=6.
Je cherche aussi à trouver l'algorithme plus complexe:
je donne en paramètre N (nombre totale de personnes), k (nombre de personnes par groupe) et x: le nombre d'itérations que je veux faire. On enlevérais la contrainte du sans répétition mais la contrainte resterais que chaque personne doit avoir rencontré le plus de monde possible aprés les x itérations (donc idéalement, maximum 2 personnes qui se connaissent déja dans un groupe donné)
Merci
Partager