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 :

Couplages de sous-ensembles


Sujet :

Algorithmes et structures de données

  1. #1
    Membre actif
    Profil pro
    Inscrit en
    Février 2003
    Messages
    926
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2003
    Messages : 926
    Points : 273
    Points
    273
    Par défaut Couplages de sous-ensembles
    Bonjour,

    je programme actuellement en python et je voudrais faire l’algorithme suivant :

    j'ai 2 ensembles E et F contenant chacun le même nombre de sous-ensembles :

    E = { (a), (a,b), (d), (a,g,h,k), (e,j,d), (d), ... }
    F = { (c,e), (d,c) (d), (e,j,k), (c,e,h,d), ((f,b),... }

    Je voudrais savoir s'il est possible de marier chaque élément de E avec un élément distinct de F :
    - chaque élément de E ne doit être couplé qu'à un seul élément de F et réciproquement (polygamie interdite).
    - il ne doit pas rester d'élément célibataire.

    Exemples :

    (a) + (a,f,g) = (a)
    (d) + (d) = (d)
    (f,j,e) + (j,a,d,u,e) = (j,e)
    (h,c,d,e,g) + (d,c,k,l,h) = (c,d,h)

    (e,u,l) + (a,d,j) = 0 (non mariable)

    Sauriez-vous comment on traite ce problème, svp. Merci pour votre aide.

    Cordialement
    Arsène

  2. #2
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    Par défaut
    Bonjour

    contenant chacun le même nombre de sous-ensembles :
    Le même nombre de sous-ensembles ou le même nombre d'éléments ?
    Ça part mal. Moi, je vois un ensemble contenant des n-uplets. Pas de sous-ensemble. Voulais-tu dire cela : { {a}, {a,b},... } ?

    Je voudrais savoir s'il est possible de marier chaque élément de E avec un élément distinct de F
    S'il y en a le même nombre, ça part bien. A priori, oui.

    - il ne doit pas rester d'élément célibataire.
    Où ça ? Mais de quoi tu parles ? Quel est le résultat de ton algorithme ?

    Exemples :

    (a) + (a,f,g) = (a)
    Ni E, ni F ne contiennent (a,f,g). Quel exemple !

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    (a) + (a,f,g) = (a)
    (...)
    (f,j,e) + (j,a,d,u,e) = (j,e)
    Des fois tu fais la réunion (ligne 1), et des fois tu fais l'intersection (ligne 3). Quelle est la règle ?

    Sauriez-vous comment on traite ce problème, svp.
    Avec une boucle. Où est le problème ? Qu'est-ce qui te bloque ?
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Membre actif
    Profil pro
    Inscrit en
    Février 2003
    Messages
    926
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2003
    Messages : 926
    Points : 273
    Points
    273
    Par défaut
    je considérai (a) (b,d) (f,g,h) comme étant des sous-ensembles. Effectivement, je viens de me rendre compte que ça s'appelle des tuples en python. Je rectifie donc :

    j'ai 2 ensembles E et F qui contiennent le même nombre de tuples.

    Et voici ma règle : un tuple de l'ensemble E et un tuple de l'ensemble F ne peuvent s'épouser que s'ils ont au moins un élément en commun.

    C'est ce que j'ai voulu montrer dans mon exemple.

    Et pour la solution :

    Citation Envoyé par Flodelarab Voir le message
    Avec une boucle. Où est le problème ? Qu'est-ce qui te bloque ?
    Je ne suis pas certain qu'une simple boucle suffise car y'a beaucoup trop de combinaisons en jeu et ça peut prendre un temps infini.

  4. #4
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    Par défaut
    Au temps pour moi. Il n'y a pas de réunion. Il n'y a que des intersections.

    y'a beaucoup trop de combinaisons en jeu et ça peut prendre un temps infini.
    La question que tu poses relève des mathématiques combinatoires.
    Et c'est souvent que les quantités s'envolent dans ce domaine.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    >>> a = set([1, 2, 3, 4, 5])                                                                                                                                                                                                                                                                                                   
    >>> b = set([4, 5, 6, 7, 8])                                                                                                                                                                                                                                                                                                   
    >>> a.intersection(b)                                                                                                                                                                                                                                                                                                          
    set([4, 5])
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  5. #5
    Membre actif
    Profil pro
    Inscrit en
    Février 2003
    Messages
    926
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2003
    Messages : 926
    Points : 273
    Points
    273
    Par défaut
    Merci de m'avoir indiquer la fonction .intersection. Je crois qu'elle devrait me servir.

    Je vais essayer d'étudier une piste --> Pour chaque élément contenu dans les tuples, je vais déterminer le nombre de mariages qu'il lui est possible de faire.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    a peut faire x mariages, b peut faire y mariages, etc...
    Après je réfléchirai. J'espère que je vais pas tomber dans une impasse.

    J'ai au total 9 éléments et 76 tuples différents. Mais les ensembles peuvent contenir plusieurs fois le même tuple.

  6. #6
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    S'il y a n tuples dans chaque ensemble, alors il y a n! combinaisons à analyser, ce n'est pas énorme. Enfin, ça dépend de la valeur de n. Si n peut dépasser 1000, alors ça fait effectivement beaucoup de combinaisons.
    Tu peux utiliser des astuces pour diminuer les temps des traitements.
    Sur l'exemple initial, tu retrie tes 2 ensembles :

    E = { (a), (d), (d), (a,b), (e,j,d), (a,g,h,k), ... }
    F = { (d), (c,e), (d,c), (f,b), (e,j,k), (c,e,h,d), ... }

    Tu mets en premier les éléments les plus difficiles à marier (les tuples ayant peu d'éléments). Ainsi, les combinaisons qui mènent à des impasses seront plus vite identifiées.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  7. #7
    Membre actif
    Profil pro
    Inscrit en
    Février 2003
    Messages
    926
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2003
    Messages : 926
    Points : 273
    Points
    273
    Par défaut
    Merci pour cette suggestion. Je la prendrai en considération. Le fait qu'il n'y ait que 9 éléments simplifie surement le problème. Je pense que c'est un cas très intéressant à étudier. Peut-être que le problème est déjà connu en mathématique, dans la théorie des ensembles... J'espère en tous cas que j'arriverai à trouver la solution.

  8. #8
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    Par défaut
    Citation Envoyé par tbc92 Voir le message
    S'il y a n tuples dans chaque ensemble, alors il y a n! combinaisons à analyser, ce n'est pas énorme
    Noooon. Beaucoup moins. n2.
    Pour chaque tuple de E, il prend un tuple de F.
    C'est une multiplication.

    Voilà pourquoi je ne comprends pas la tergiversation.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  9. #9
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    Pour le premier élément de n, on a n conjoints possibles.
    Puis n-1 pour le 2ème élément
    Puis n-2 pour le 3ème,
    etc, on arrive à n!

    Quoi qu'il en soit, avec 9 éléments seulement, un recensement de toutes les combinaisons devrait aller assez vite. Si tu acceptes que ton traitement dure 4 ou 5 secondes, ça ne devrait pas poser de problème.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  10. #10
    Membre actif
    Profil pro
    Inscrit en
    Février 2003
    Messages
    926
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2003
    Messages : 926
    Points : 273
    Points
    273
    Par défaut
    Je mets en exemple 3 ensembles ayant chacun 48 tuples.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    E = { (b,c,e,f),(b,f),(b,d,f,j),(c,h),(g),(a,d,f),(f,j),(d,f,g),(a,f),(c,h),(d,g),(f),(d,g),(f),(d,f,g),(f),(d,g),(d,f,h),(f),(c,h),(d,g),(a,f),(b,f),(b,d,f,j),(c,h),(g),(a,d,f),(f,j),(a,g),(d,f,h),(a,f,j),(c,h),(a,g),(d,f,h),(f),(d,f,h),(f),(d),(b,d,f),(b),(j),(h),(j),(g),(a,d,f),(a,f),(d,g),(f)}
    a=10 fois , b=8 fois, c=7 fois, d=19 fois, e=1 fois, f=29 fois, g=13 fois, h=11 fois, j=8 fois.
    F = { (f,h),(a,f,j),(a,d,f),(f),(a),(d,h),(b,d,f,j),(a,f),(d,g),(d,h),(h),(c,f,h),(j),(d),(b,d,f),(c),(d,h),(j),(f,h),(a,f,j),(a,d,f),(a,f),(g),(a,f),(h),(d,f,h),(j),(c),(d,f,h),(j),(f,h),(a,f,j),(a,d,f),(f),(f,g),(a,d),(a,f,j),(f,h),(a,f,j),(d,f,h),(f,j),(d,g),(d,f,h),(f),(c),(d,g),(d,f),(f)}
    a=14 fois;  b=3 fois;  c=5 fois;  d=19 fois;  e=1 fois;  f=39 fois;  g=6 fois;  h=15 fois;  j=12 fois.
    G = {(a,f),(c),(a,f),(j),(a,f),(d,f),(f),(h),(b,f),(g,h),(j),(b),(c,h),(a,d,f),(c),(h),(j),(a,j),(b,f,g),(h),(h),(d),(f),(d,h),(b,d,f,j),(a,f),(c),(d,h),(b,d,f,j),(a),(d,g),(d,h),(d,h),(f),(h),(d,g),(h),(h),(f,h),(j),(d,h),(b,d,f),(j),(d,f,h),(f),(c),(d,h),(f)}
    a=8 fois;  b=7 fois;  c=6 fois;  d=16 fois;  e=1 fois;  f=28 fois;  g=5 fois;  h=18 fois;  j=9 fois.
    Si je veux marier F et G, pour le premier tuple de F j'ai :

    1 - (39*28)+(6*18) = 1092 + 108 = 1200 possibilités.
    ...
    48 - ... x possibilités

    Pour l'élément a, il y a : 14*8 = 112 possibilités
    Pour l'élément b, il y a : 3*7 = 21 possibilités
    Pour l'élément c, il y a : 5*6 = 30 possibilités
    Pour l'élément d, il y a : 19*16 = 304 possibilités
    Pour l'élément e, il y a : 1*1 = 1 possibilité
    Pour l'élément f, il y a : 39*28 = 1092 possibilités
    Pour l'élément g, il y a : 6*18 = 108 possibilités
    Pour l'élément h, il y a : 15*18 = 270 possibilités
    Pour l'élément j, il y a : 12*9 = 108 possibilités

    Par ailleurs, si on utilise n! ici, on obtient le chiffre astronomique de 48!

    Et pour un élément, on a : 48*47*46*45*44*43*42*41*40 = 608 588 457 523 200 possibilités théoriques, en admettant que chaque tuple porte un nom pour le différencier du voisin.

  11. #11
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Couplages de sous-ensembles
    Bonjour,

    Tu veux établir une bijection entre les Tuples de (E) et ceux de (F), la correspondance entre deux listes données (Ei, Fj) n'étant envisageable que si l'intersection de ces dernières ne se réduit pas à l'ensemble vide:
    Citation Envoyé par Arsene12 Voir le message
    j'ai 2 ensembles E et F qui contiennent le même nombre de tuples.

    Et voici ma règle : un tuple de l'ensemble E et un tuple de l'ensemble F ne peuvent s'épouser que s'ils ont au moins un élément en commun ...
    Le nombre de solutions à tester reste cependant très en-dessous des estimations précédentes, compte tenu de la rareté de certains éléments communs: il suffit pour s'en convaincre d'observer dans le détail l'exemple proposé.
    Si l'on s'en tient aux deux premiers ensembles (E, F), les nombres d'occurrences des divers éléments sont dans l'ordre croissant:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
     Ne=1 ; Nc=7 ; Nb=8 ; Nj=8 ; Na=10 ; Nh=11 ; Ng=13 ; Nd=19 ; Nf=29
    et l'on peut entreprendre l'inventaire des combinaisons selon cette séquence, en reprenant l'idée suggérée par tbc92 (#6)

    Citation Envoyé par tbc92 Voir le message
    ... Tu mets en premier les éléments les plus difficiles à marier (les tuples ayant peu d'éléments). Ainsi, les combinaisons qui mènent à des impasses seront plus vite identifiées.
    ... et que personne n'a reprise par la suite.

    Une matrice carrée de booléens, présentant dans chacune de ses dimensions la liste complète de tous les tuples de chaque ensemble, constitue un bon outil de sélection; il s'agit d'une matrice dont toutes les éléments (Mij) présentant la valeur True
    correspondent à deux tuples (Ei, Ej) à intersection non vide.
    En commençant systématiquement par les lignes et les colonnes les moins peuplées, il ne doit plus rester, en fin d'élimination, qu'un seul élément à la valeur True dans chaque ligne et chaque colonne: la matrice obtenue représente la bijection cherchée.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  12. #12
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    Je viens de l'implémenter.
    Dans un premier temps , j'avais compris qu'il y avait 9 tubles, mais en fait, c'est 48.
    Sans l'optimisation suggérée #6, le traitement dure quelques minutes.
    Avec l'optimisation en question, c'est instantané.

    Le code ( ce n'est pas du python, mais ça doit pouvoir se traduire en Python.

    Déclaratives globales :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    un_tuple est une Structure
    	nvrai est un entier
    	tt est un tableau de 9 booléens 
    FIN
    ttuples est un tableau de 2 par 48 un_tuple 
     
    un_scenar est une Structure 
    	n_maries est un entier 
    	tb_maries est un tableau de 48 entiers
    	tb_inv_maries est un tableau de 48 entiers
    FIN
    tb_scenar est un tableau de 0 un_scenar
    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
    tq est un tableau de 48 un_tuple
    ch1, ch2, alp  est une chaîne 
    tch est un tableau de 2 chaînes
    i, j, k , po  est un entier 
    fini est un booléen
     
    alp = "ABCDEFGHJ"
    tch[1] = [
    (b,c,e,f),(b,f),(b,d,f,j),(c,h),(g),(a,d,f),(f,j),(d,f,g),(a,f),(c,h),(d,g),(f),(d,g),(f),(d,f,g),(f),(d,g),(d,f,h),(f),(c,h),(d,g),(a,f),(b,f),(b,d,f,j),(c,h),(g),(a,d,f),(f,j),(a,g),(d,f,h),(a,f,j),(c,h),(a,g),(d,f,h),(f),(d,f,h),(f),(d),(b,d,f),(b),(j),(h),(j),(g),(a,d,f),(a,f),(d,g),(f)
    ]
    tch[2] = [
    (f,h),(a,f,j),(a,d,f),(f),(a),(d,h),(b,d,f,j),(a,f),(d,g),(d,h),(h),(c,f,h),(j),(d),(b,d,f),(c),(d,h),(j),(f,h),(a,f,j),(a,d,f),(a,f),(g),(a,f),(h),(d,f,h),(j),(c),(d,f,h),(j),(f,h),(a,f,j),(a,d,f),(f),(f,g),(a,d),(a,f,j),(f,h),(a,f,j),(d,f,h),(f,j),(d,g),(d,f,h),(f),(c),(d,g),(d,f),(f)
    ]
     
    tup est un_tuple
    tup0 est un_tuple
     
    POUR i = 1 A 2
    	ch1 = tch[i]
    	ch1 = Remplace ( ch1, RC , "")
    	ch1 = Remplace (ch1, "(", "")
    	ch1 = Remplace (ch1, ")", TAB)
    	ch1 = Majuscule(ch1) 
    	POUR j = 1 A 48
    		ch2 = ExtraitChaîne(ch1,j,TAB)
    		tup = tup0
    		POUR TOUTE CHAÎNE ch0 DE ch2 SEPAREE PAR ","
    			SI "A" <= ch0 _ET_ ch0 <= "J" ALORS 
    				po = Position ( alp, ch0)
    				tup.nvrai++
    				tup.tt[po]= Vrai
    			FIN
    		FIN
    		tq[j] = tup
    	FIN
    	TableauTrie(tq, ttMembre, "nvrai")
    	POUR j = 1 A 48
    		ttuples[i,j] = tq[j]
    	FIN
    FIN
     
    POUR i = 1 A 2 
    	POUR j  = 1 A 48
    		ch1 = " " 
    		POUR k = 1 A 9
    			SI ttuples[i,j].tt[k] ALORS 
    				ch1 = ch1 + "1" 
    			SINON
    				ch1 = ch1 + " "
    			FIN
    		FIN
    		Trace ( " i,j=" + i + "," + j + " "  + ch1)
    	FIN
    FIN
    qsc est un_scenar
    qsc.n_maries = 0
    TableauAjouteLigne(tb_scenar, qsc)
    TANTQUE fini = Faux
    	i = TableauOccurrence(tb_scenar)
    	SI i = 0 ALORS 
    		Erreur ( " pas de solution")
    		fini = vrai
    	FIN
    	qsc = tb_scenar[i]
    	SI qsc.n_maries = 48 ALORS 
    		Info ( "trouve")
    		f_dessine(qsc)
    		fini = Vrai 
    	SINON
    		TableauSupprime(tb_scenar,i)
    		f_traite ( qsc )
    	FIN
    FIN
    Et les sous-procédures :
    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
    PROCEDURE f_traite(qsc est un_scenar )
    nm est un entier 
    nm = qsc.n_maries
    nvsc est un_scenar
    nm++
    nvsc.n_maries = nm
     
    i,j est un entier 
    i = nm
    POUR j = 48 A  1 PAS -1 
    	SI qsc.tb_inv_maries[j] = 0 ALORS 
    		SI f_mariable ( i, j ) ALORS 
    			nvsc = qsc
    			nvsc.n_maries = nm
    			nvsc.tb_maries[i] = j	
    			nvsc.tb_inv_maries[j] = i	
    			TableauAjouteLigne(tb_scenar, nvsc)
    		FIN
    	FIN
    FIN
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    PROCEDURE f_mariable(i,j)
    k est un entier 
    POUR k = 1 A 9
    	SI ttuples[1,i].tt[k] = Vrai _ET_ ttuples[2,j].tt[k] = Vrai ALORS RENVOYER Vrai
    FIN
    RENVOYER Faux
    Le 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
    h marié avec h
    f marié avec f
    f marié avec f
    f marié avec f
    g marié avec g
    g marié avec dg
    g marié avec dg
    j marié avec j
    d marié avec d
    f marié avec f
    f marié avec fh
    b marié avec bdf
    f marié avec af
    f marié avec af
    j marié avec j
    ch marié avec c
    dg marié avec dh
    dg marié avec dh
    af marié avec a
    ch marié avec c
    dg marié avec dh
    af marié avec af
    bf marié avec fh
    fj marié avec j
    bf marié avec fg
    ch marié avec c
    dg marié avec ad
    fj marié avec j
    ag marié avec dg
    ch marié avec h
    ch marié avec fh
    ag marié avec afj
    af marié avec df
    dg marié avec dfh
    dfh marié avec fj
    adf marié avec fh
    dfh marié avec adf
    dfh marié avec afj
    bdf marié avec afj
    afj marié avec dfh
    dfh marié avec adf
    dfg marié avec afj
    dfg marié avec dfh
    adf marié avec cfh
    adf marié avec dfh
    bcef marié avec afj
    bdfj marié avec adf
    bdfj marié avec bdfj
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  13. #13
    Membre actif
    Profil pro
    Inscrit en
    Février 2003
    Messages
    926
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2003
    Messages : 926
    Points : 273
    Points
    273
    Par défaut
    Merci beaucoup pour vos solutions. J'ai construit une matrice et ça m'a permis en effet de mieux cerner le problème :
    Nom : Matrice.jpg
Affichages : 245
Taille : 831,0 Ko

    Il faut commencer par les lignes et les colonnes qui contiennent le moins de VRAI. Dans le cas ci-dessus, on commence par la colonne C5 (1 solution), puis on continue par les lignes L10 et 12 (2 solutions) et ainsi de suite...

    Je vais maintenant essayer de traduire cette méthode en python.

    On doit faire en l’occurrence 48 sélections. A chaque sélection, on élimine une ligne et une colonne. Et le nombre de choix décline au fur et à mesure qu'on avance. Mais le nombre de choix possibles reste quand même très grand.

  14. #14
    Membre actif
    Profil pro
    Inscrit en
    Février 2003
    Messages
    926
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2003
    Messages : 926
    Points : 273
    Points
    273
    Par défaut
    Il faut décomposer la matrice principale en n matrices (n étant le nombre d'élements distincts constituant les tuples).

    Les tuples comprennent les éléments n1, n2, n3, n4,....

    Pour chaque matrice d'élément n, il existe X solutions que l'on peut calculer ainsi :

    x = nombre d'éléments n1 dans la rangée colonne
    y = nombre d'éléments n1 dans la rangée ligne

    si x < y : X = (x*y) + (x-1)*(y-1) + (x-2)*(y-2) + (x-3)*(y-3) + ... + (y-x-1)
    si y < x : X = (y*x) + (y-1)*(x-1) + (y-2)*(x-2) + (y-3)*(x-3) + ... + (x-y-1)

  15. #15
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    Commençons par les tuples constitués d'un seul individu, dans l'ensemble E.
    On a par exemple le 48èeme tuple qui est (f). On peut le marier avec différents tuples de F, mais autant le marier avec le 48ème tuple de F, c'est à dire avec (f). On est sûr de ne pas compromettre la suite du traitement.
    On a 9 tuples comme ça constitués d'un seul élément, qu'on peut marier avec un tuple identique de F.

    Reste donc 39 tuples dans E et dans F.
    On continue en traitant toujours les tuples les plus courts. On a (g). Théoriquement, il y a 39 conjoints possibles. dans les faits, seuls 4 sont compatibles (dg), (dg), (dg) et (fg). Et donc en fait, seulement 2 options (dg) ou (fg). Le nombre de combinaisons à analyser n'est donc pas aussi élevé qu'en théorie, loin s'en faut. Et en plus, inutile d'analyser toutes les combinaisons... Dès la 10ème ou 20ème, on tombe sur une combinaison valide.

    A condition bien sûr qu'on marie d'abord les éléments difficiles à marier, et qu'on garde pour la fin les éléments les plus faciles à marier.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  16. #16
    Membre actif
    Profil pro
    Inscrit en
    Février 2003
    Messages
    926
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2003
    Messages : 926
    Points : 273
    Points
    273
    Par défaut
    À partir du tableau que j'ai affiché ci-dessus, il existe 2 méthodes pour savoir si les 2 ensembles peuvent appliquer la règle que j'ai défini au tout début.

    1 ère méthode :

    on clique sur une case VRAI et on élimine la ligne et la colonne qui la contiennent. L'opération doit être réaliser n fois, n correspondant au nombre de tuples d'un ensemble (Rappelons que les 2 ensembles ont le même nombre de tuples, c'est-à-dire qu'il y a autant de colonnes que de lignes dans la matrice qui les associe). À la fin, il ne doit rester qu'une case, et ça doit être une case VRAI.

    -Remarque : Avec cette méthode on doit cliquer en priorité sur les lignes ou les colonnes contenant le plus petit nombre de case VRAI.

    2 ème méthode :

    on permute les lignes entre elles ou les colonnes entre elles de façon à obtenir une grande diagonale de n cases ; ces cases sont toutes des cases VRAI.

  17. #17
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    Oui, ces 2 méthodes sont bonnes.
    Mais la difficulté est ailleurs. La difficulté, c'est de pouvoir 'tatonner' : tu cliques sur une case, puis une autre qui est compatible... etc, et si à un moment, tu arrives à une impasse, il faut annuler le dernier clic, et parcourir une autre branche. C'est du parcours d'arbre.
    C'est ce que j'ai fait dans le code proposé dimanche soir.
    L'élément E1, je peux le marier avec qui ? disons qu'on peut le marier avec F4 F10 F12 et F30.
    On va explorer le scénario E1 marié avec F4 et on va garder en mémoire les 3 autres scénarios E1F10 E1F12 et E1F30

    Puis considérant que E1 est marié avec F4, je vais recenser tous les éléments que je peux marier à E2. Et j'alimente un tableau avec tous les scénarios possibles.
    Les scénarios qui marient E1 à F1 F12 ou F30 ne sont quasiment pas développés, seul le 1er couple est créé. Par contre le scénario E1F4 est développé autant que possible, soit jusqu'à une solution, soit jusqu'à une impasse.

    En tout, ça tient en une trentaine de lignes de code.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  18. #18
    Membre actif
    Profil pro
    Inscrit en
    Février 2003
    Messages
    926
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2003
    Messages : 926
    Points : 273
    Points
    273
    Par défaut
    Je ne crois pas que le parcours d'arbre (1ère méthode) soit la solution la plus adaptée car elle peut parfois être très longue. Il doit y'avoir une solution "mathématique" au problème. Elle se trouve je pense dans la 2ème méthode.

    Mon casse-tête ressemble un peu au rubik's cube car on peut le résoudre par une méthode de permutations.

    Je sais pas comment la résolution du rubik's cube se traduit en langage algorithmique. Ce que je sais par contre, c'est que le rubik's cube peut sembler long et complexe à résoudre du fait de son nombre très élevé de permutations mais qu'il existe en fait différentes techniques qui permettent de le résoudre facilement et rapidement.

    Autre analogie : si on inverse les couleurs de 2 carrés dans le rubik's cube, ça peut entraîner l'impossibilité de le résoudre. C'est pareil pour mon casse-tête : c'est un peu comme essayer de deviner s'il n'y a pas eut inversion de 2 couleurs.

  19. #19
    Membre confirmé
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Points : 554
    Points
    554
    Par défaut
    Citation Envoyé par Arsene12 Voir le message
    Il doit y'avoir une solution "mathématique" au problème.
    Effectivement, il y en a une. C'est un problème de couplage parfait dans un graphe biparti. Cela peut par exemple être résolu par l'algorithme hongrois en partant de la matrice des appariements possibles avec un coût 1 quand c'est possible et 0 quand cela ne l'est pas.

  20. #20
    Membre actif
    Profil pro
    Inscrit en
    Février 2003
    Messages
    926
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2003
    Messages : 926
    Points : 273
    Points
    273
    Par défaut
    Merci beaucoup de m'avoir indiqué ce théorème. J'ai été voir un cours sur la méthode hongroise sur YouTube.



    Quand une solution existe, cet algorithme permet, par le biais de transaction, d'obtenir une grille où toute les lignes et toutes les colonnes contiennent au moins une case composée d'un 0. Or dans ma grille à moi, toutes les cases sont composés d'un 0 (case VRAI) ou d'un 1 (case FAUX). On peut donc du premier coup d’œil savoir si la grille n'est pas soluble. Elle ne l'est pas quand y'a au moins une colonne ou une ligne qui n'est composée que de case FAUX. Pour que la grille soit soluble, il faut en plus que par le biais des permutation de lignes et de colonnes, il soit possible d'obtenir une diagonale de case VRAI.

Discussions similaires

  1. sous ensembles & permutation de liste
    Par LlufRuS dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 06/12/2006, 11h22
  2. Réponses: 2
    Dernier message: 27/01/2006, 10h48
  3. sous ensemble d'une liste
    Par adel25 dans le forum C++
    Réponses: 1
    Dernier message: 23/08/2005, 16h50
  4. [DBGrid] Affichage d'un sous-ensemble de données
    Par Jean-Jacques Engels dans le forum Bases de données
    Réponses: 3
    Dernier message: 02/09/2004, 17h31
  5. Sous-ensembles de tuples
    Par HPJ dans le forum MS SQL Server
    Réponses: 4
    Dernier message: 07/10/2003, 17h24

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