Nombre d'itérations maximum avec répartition sans répétition

Version imprimable

18/11/2020, 23h36
Florian.L

Nombre d'itérations maximum avec répartition sans répétition

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
19/11/2020, 09h28
WhiteCrow

Citation:

Envoyé par Florian.L

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

Bonjour,
Ce que tu demandes a déjà été étudié, dans la littérature c'est ce qu'on appelle un block design, plus précisément dans ton cas un (near-) resolvable balanced incomplete block design. Pour une intro et une bibliographie → https://en.wikipedia.org/wiki/Block_design

Citation:

Envoyé par Florian.L

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.

Il y a pas mal de résultats concernant les BIBD mais c'est un problème complexe en général.
Une bonne source sur le sujet est : Handbook of Combinatorial Designs Second Edition, Charles J. Colbourn & Jeffrey H. Dinitz.
Si tu as du mal à le trouver, tu peux me contacter en MP.

Citation:

Envoyé par Florian.L

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

L'approche naïve est simple à comprendre et dans le cas général c'est un problème NP. Il n'y a pas de «formule magique» 😅
Donc, l'approche naïve consiste à représenter les N participants au tournoi par les sommets d'un graphe, deux sommets étant reliés par une arrête ssi ils n'ont jamais joué ensemble (i.e. n'ont jamais fait partie du même groupe de k personnes). Une itération consiste donc à trouver une partition du graphe en (N/k) k-cliques, déconstruire ces k-cliques = supprimer les arêtes de ces k-clique dans le graphe et recommencer.

Avoir des conditions plus lâches est simplement modélisable aussi :
Autoriser des groupes où il y a deux participants au plus qui auraient déjà pu se rencontrer est utiliser une k-clique moins une arête comme sous graphe cherché (on parle de sous graphe isomorphe).
Autoriser un groupe de participants morts (des participants qui ne jouent pas à un tour) revient à considérer comme valide une solution où tu as un résidu de sommets que tu ne peux pas utiliser.
…

Je te conseille très vivement la lecture du livre dont je t'ai donné la référence, il s'agit d'une étude très détaillée et tu y trouveras certainement ton bonheur.

Cela est-il bon ?
Tableaux de chaînes; résult dans ZZ()

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
A(K); B(L); C(M); D(N)...ect
Pour x=0 to K
  Pour y=0 to L
    na=na+1: ZZ(na)=A(x)+B(y)
  next y
  Pour y=0 to M
    na=na+1: ZZ(na)=A(x)+C(y)
  next y
  Pour y=0 to N
    na=na+1: ZZ(na)=A(x)+D(y)
  next y
  ...ect
Next x
...ect

Nombr iter=K*L*M*N + L*M*N + M*N

20/11/2020, 04h03
Florian.L

Merci beaucoup pour ta réponse détaillé whitecrow.

Je me doutais que ce genre de problème avait déja été étudié mais dans mes recherches, je n'avais rien trouvé... merci de me pointer la bonne direction.
Je vais faire un peu de lecture :)

Citation:

L'approche naïve est simple à comprendre et dans le cas général c'est un problème NP. Il n'y a pas de «formule magique» 😅
Donc, l'approche naïve consiste à représenter les N participants au tournoi par les sommets d'un graphe, deux sommets étant reliés par une arrête ssi ils n'ont jamais joué ensemble (i.e. n'ont jamais fait partie du même groupe de k personnes). Une itération consiste donc à trouver une partition du graphe en (N/k) k-cliques, déconstruire ces k-cliques = supprimer les arêtes de ces k-clique dans le graphe et recommencer.

J'ai un peu du mal à comprendre la dernière phrase... Ma maitrise des graphes est loin d'être parfaite... et j'ai jamais trop expérimenté dessus depuis mes études sup (c-a-d depuis un moment mantenant :) )

Citation:

Cela est-il bon ?
Tableaux de chaînes; résult dans ZZ()

Je n'ai pas compris ce que tu cherchais a faire ?
20/11/2020, 08h17
WhiteCrow

3 pièce(s) jointe(s)
Citation:

Envoyé par Florian.L

J'ai un peu du mal à comprendre la dernière phrase... Ma maitrise des graphes est loin d'être parfaite... et j'ai jamais trop expérimenté dessus depuis mes études sup (c-a-d depuis un moment mantenant :) )

Par exemple si tu représente l'état d'un tournoi par un graphe G où les sommets représentent les participants et les arêtes la relation «n'a jamais joué dans le même groupe que» alors si tu lui trouve un sous graphe qui est une clique, un ensemble de sommets tous reliés entre eux = un sous-graphe complet si tu veux, composée de k sommets, une k-clique, alors tu auras identifié un groupe de personnes tel qu'aucune d'entre elles n'ait jamais joué avec une autre. Par exemple si tu trouves un sous graphe isomorphe à K4 →
Pièce jointe 584514 alors tu auras trouvé 4 personnes qui n'ont pas encore joué ensembles.

Rechercher un sous graphe complet ayant k sommets est le problème de la liste de toutes les k-cliques d'un graphe. Mais on peut aussi essayer de chercher n'importe quelle autre «forme» de sous graphe. Par exemple si tu cherches
Pièce jointe 584515 alors tu cherches un groupe de 4 personnes dans lequel chaque personne rencontre 2 nouvelles personnes et une déjà rencontrée auparavant.
Si tu cherches
Pièce jointe 584516 alors cela revient à cherche les groupes de 4 personnes parmi lesquelles 3 ne se sont jamais rencontrées (le triangle) et une qui a rencontré toutes les autres (le point isolé).

Donc si tu veux créer un tournoi avec un mode dégradé, l'idée sera de commencer à essayer de construire une solution avec des cliques et si tu ne trouves rien alors d'essayer de trouver des sous graphes moins contraignants comme ceux ci-dessus.

Sinon, en ce qui concerne les «morts», il s'agit simplement de ne pas chercher à partitionner les graphes qui ne peuvent pas l'être comme les tournoi avec par exemple 14 participants en format des groupes de 3 personnes. Tu auras forcément 14 mod 3=2 personnes qui restent ne pourront former un groupe de 3.
Deux solutions s'offrent à toi :
- soit tu utilises l'algorithme et tu considère qu'un résidu de 2 personnes est ok, ou d'une façon similaire tu supprimes deux personnes avant de lancer l'algo pour un tour, tu changes à chaque tour les personnes supprimées ;
- tu ajoutes des personnes fictives que tu enlèves par la suite des résultats.
Si tu en viens à implémenter cette solution, je pense que commencer à le faire en python/julia permettrait au moins de la valider. Que ce soit python ou julia, tu auras à ta disposition des bibliothèque de manipulation de graphe. Peut-être qu'il ne serait pas trop compliqué de le faire dans des env plus orientés math comme sagemath ? plus performants avec du C++ ? mais autant commencer par un proof of concept 😁
20/11/2020, 16h52
Florian.L

Je pense comprendre un peu mieux Mais il y a un lien que je vois pas:

Imaginons N=16 et K=4.
Le nombre d'itérations possible est 5.

# ITERATION 1
Group 1: A1 A2 A3 A4
Group 2: B1 B2 B3 B4
Group 3: C1 C2 C3 C4
Group 4: D1 D2 D3 D4

# ITERATION 2
Group 1: A1 B1 C1 D1
Group 2: A2 B2 C2 D2
Group 3: A3 B3 C3 D3
Group 4: A4 B4 C4 D4

# ITERATION 3
Group 1: A1 B2 C3 D4
Group 2: A2 B1 C4 D3
Group 3: A3 B4 C1 D2
Group 4: A4 B3 C2 D1

# ITERATION 4
Group 1: A1 B3 C4 D2
Group 2: A2 B4 C3 D1
Group 3: A3 B1 C2 D4
Group 4: A4 B2 C1 D3

# ITERATION 5
Group 1: A1 B4 C2 D3
Group 2: A2 B3 C1 D4
Group 3: A3 B2 C4 D1
Group 4: A4 B1 C3 D2

Maintenant, si dans l'itération 3, on aurait fait cela à la place:
# ITERATION 3
Group 1: A1 B2 C3 D4
Group 2: A2 B3 C4 D1
Group 3: A3 B4 C1 D2
Group 4: A4 B1 C2 D3

eh bien, il se trouve qu'il n'est plus possible d'atteindre les 5 itérations.

Avec l'utilisation des graphes, je vois pas comment l'éviter ? Il faudrait backtrack a l'itération incorrect... mais comment savoir qu'elle est incorrecte ?

J'ai lu la page Wikipédia sur le Block design... j'ai pas tout compris, mon niveau de math est pas assez élevé j'en ai peur. MAis j'Ai essayer de comprendre ce que je pouvais mais je n'ai pas trouvé un début de réponse/ d'équation qui me pourrait me donner la réponse a la question:
J'aimerais savoir le nombre d'itération maximum que l'on peut faire pour N et k donné sans répétion.

Dans les exemples données, il y a de la répétition.
20/11/2020, 18h05
WhiteCrow

Citation:

Envoyé par Florian.L

Je pense comprendre un peu mieux Mais il y a un lien que je vois pas:

Imaginons N=16 et K=4.
Le nombre d'itérations possible est 5.

# ITERATION 1
Group 1: A1 A2 A3 A4
Group 2: B1 B2 B3 B4
Group 3: C1 C2 C3 C4
Group 4: D1 D2 D3 D4

# ITERATION 2
Group 1: A1 B1 C1 D1
Group 2: A2 B2 C2 D2
Group 3: A3 B3 C3 D3
Group 4: A4 B4 C4 D4

# ITERATION 3
Group 1: A1 B2 C3 D4
Group 2: A2 B1 C4 D3
Group 3: A3 B4 C1 D2
Group 4: A4 B3 C2 D1

# ITERATION 4
Group 1: A1 B3 C4 D2
Group 2: A2 B4 C3 D1
Group 3: A3 B1 C2 D4
Group 4: A4 B2 C1 D3

# ITERATION 5
Group 1: A1 B4 C2 D3
Group 2: A2 B3 C1 D4
Group 3: A3 B2 C4 D1
Group 4: A4 B1 C3 D2

Maintenant, si dans l'itération 3, on aurait fait cela à la place:
# ITERATION 3
Group 1: A1 B2 C3 D4
Group 2: A2 B3 C4 D1
Group 3: A3 B4 C1 D2
Group 4: A4 B1 C2 D3

eh bien, il se trouve qu'il n'est plus possible d'atteindre les 5 itérations.

Avec l'utilisation des graphes, je vois pas comment l'éviter ? Il faudrait backtrack a l'itération incorrect... mais comment savoir qu'elle est incorrecte ?

On se restreint à ton cadre plus restrictif que le cadre général. Tu sais que s'il existe une solution alors tu auras exactement (N-1)/(k-1) itérations chacune produisant N/k groupes de k participants.
C'est un algo récursif. Le backtrack se fait naturellement, il y a deux «boucles», une pour construire les groupes et une pour construire les itérations.
Dans la boucle pour construire les groupes, on cherche une k-clique (qui est le groupe) et on supprime les sommets du groupe dans le graphe avant de poursuivre. On réussit à construire une itération si on ne peut plus trouver de k-clique car le graphe est vide.
Dans la boucle des itérations, on passe au graphe suivant en supprimant les arêtes des cliques trouvées. Tu as trouvé une solution complète uniquement si tu arrives à avoir un graphe sans arêtes. Si ce n'est pas le cas alors tu avertis le niveau supérieur et il passe à la recherche de groupes suivante.
Tu ne sais pas directement à l'itération 3 qu'elle ne va pas aboutir … et c'est pour cela que ce problème est complexe : il n'y a pas de critères ni d'algo de construction plus direct (enfin ptêt avec le cas particulier des cliques de 1,2 ou 3 sommets, à approfondir).
Une condition nécessaire pour qu'une solution existe est que k divise N et k-1 divise N-1. Cette condition devient suffisante si N et k sont des puissance du même nombre premier.

Citation:

Envoyé par Florian.L

J'ai lu la page Wikipédia sur le Block design... j'ai pas tout compris, mon niveau de math est pas assez élevé j'en ai peur. MAis j'Ai essayer de comprendre ce que je pouvais mais je n'ai pas trouvé un début de réponse/ d'équation qui me pourrait me donner la réponse a la question:
J'aimerais savoir le nombre d'itération maximum que l'on peut faire pour N et k donné sans répétition.

Dans les exemples données, il y a de la répétition.

C'est aussi pour cela que je t'ai donné le lien vers le livre en MP. La partie qui t'intéresse est II.7 Resolvable and Near-Resolvable Designs. La page wikipedia est juste une intro pour avoir de la bibliographie et un petite idée.
Techniquement tu cherches à résoudre un RBIBD(N,k,1), en gros tu essayes de construire des ensembles de k éléments issus d'un ensemble de N éléments tels que deux ensembles n'ont qu'au plus 1 élément en commun.