Discussion :

[Arsene12]

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

[Flodelarab]

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 ?

[Arsene12]

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 :

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.

[Flodelarab]

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

[Arsene12]

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.

[tbc92]

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.

[Arsene12]

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.

[Flodelarab]

S'il y a n tuples dans chaque ensemble, alors il y a n! combinaisons à analyser, ce n'est pas énorme

Noooon. Beaucoup moins. n².
Pour chaque tuple de E, il prend un tuple de F.
C'est une multiplication.

Voilà pourquoi je ne comprends pas la tergiversation.