IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

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


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Homme Profil pro
    Développeur .NET
    Inscrit en
    mars 2003
    Messages
    93
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : Canada

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : mars 2003
    Messages : 93
    Points : 123
    Points
    123
    Par défaut 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

  2. #2
    Membre habitué
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    65
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 65
    Points : 180
    Points
    180
    Par défaut
    Citation Envoyé par Florian.L Voir le message
    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 Voir le message
    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 Voir le message
    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.

  3. #3
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    282
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 282
    Points : 210
    Points
    210
    Par défaut
    Cela est-il bon ?
    Tableaux de chaînes; résult dans ZZ()
    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
     
    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
    Savoir pour comprendre et vice versa.

  4. #4
    Membre régulier
    Homme Profil pro
    Développeur .NET
    Inscrit en
    mars 2003
    Messages
    93
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : Canada

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : mars 2003
    Messages : 93
    Points : 123
    Points
    123
    Par défaut
    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

    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 )



    Cela est-il bon ?
    Tableaux de chaînes; résult dans ZZ()
    Je n'ai pas compris ce que tu cherchais a faire ?

  5. #5
    Membre habitué
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    65
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 65
    Points : 180
    Points
    180
    Par défaut
    Citation Envoyé par Florian.L Voir le message
    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 →
    Nom : k4.png
Affichages : 61
Taille : 4,0 Ko 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
    Nom : C4.png
Affichages : 60
Taille : 2,8 Ko 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
    Nom : X.png
Affichages : 60
Taille : 1,5 Ko 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 😁

  6. #6
    Membre régulier
    Homme Profil pro
    Développeur .NET
    Inscrit en
    mars 2003
    Messages
    93
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : Canada

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : mars 2003
    Messages : 93
    Points : 123
    Points
    123
    Par défaut
    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.

  7. #7
    Membre habitué
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    65
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 65
    Points : 180
    Points
    180
    Par défaut
    Citation Envoyé par Florian.L Voir le message
    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 Voir le message

    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.

Discussions similaires

  1. Nombre d'itérations avec genmod
    Par DRADIOUF dans le forum SAS STAT
    Réponses: 0
    Dernier message: 07/12/2012, 16h07
  2. Réponses: 7
    Dernier message: 14/06/2010, 16h25
  3. Réponses: 2
    Dernier message: 07/09/2009, 16h28
  4. Combinaisons sans répétition avec VBA (suite)
    Par arnold95 dans le forum Macros et VBA Excel
    Réponses: 1
    Dernier message: 22/08/2007, 20h03
  5. Combinaisons sans répétition avec VBA
    Par arnold95 dans le forum Macros et VBA Excel
    Réponses: 3
    Dernier message: 16/08/2007, 17h23

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo