Combinaison des variables contenues dans des clusters

**BenkessiratAmina** · 30/01/2019, 20h49

Bonjour les calé,
J’espère que tout marche bien comme vous.
De mon côté pas trop, c’est pour cela que je suis là.
J’ai une petite idée que je veux formuler en un algorithme, mais je me dis que peut être ça existe un truck déjà défini.

Alors supposons que j’ai K clusters, dans chaque cluster il y a un nombre différent de variables !
Je veux avoir toute les combinaison possible en prenant à chaque fois une et une seule variable de chaque cluster !

Par exemple :
Cluster1=(1,2,3)
Cluster2=(4,5)
Cluster3=(6)
Mes combinaisons seront :
C1=(1,4,6)
C2=(1,5,6)
C3=(2,4,6)
C4=(2,5,6)
C5=(3,4,6)
C6=(3,5,6)
J’espère n’avoir oublier aucune.
Alors est ce qu’un tel algorithme existe déjà ?
Je vous remercie d’avance.

**tbc92** · 30/01/2019, 21h41

Parcours d'arbre non binaire ?

Bon, je sais, en disant ça, je parle chinois. Voici un lien qui en dit un peu plus : https://rperrot.developpez.com/artic...ctures/arbres/

**BenkessiratAmina** · 30/01/2019, 22h04

Pourquoi du chinois? je sais parfaitement ce que c'est!
En tous cas, ce n'est pas ça. Merci pour ta réponse

**tbc92** · 30/01/2019, 22h55

Ce n'est pas ça ? Pourtant tes données peuvent être représentées sous forme d'arbre, et le recensement de toutes les solutions, c'est la recherche de toutes les feuilles de l'arbre.

Sinon, pour avancer dans ton sens, Comment envisages-tu de stocker les données initiales ?
Dans ton premier message, tu disais cluster1=.... cluster2=... ce n'est pas exploitable, On va donc dire
cluster[1,1] = 1 ; cluster[1,3] = 2 ; cluster[1,3] = 3 ;
cluster[2,1] = 4 ; cluster[2,2] = 5 ;
cluster[3,1] = 6 ;
et
nb_clusters = 3
taille_cluster[1] = 3
taille_cluster[2] = 2
taille_cluster[3] = 1

Ok ?

**Flodelarab** · 30/01/2019, 22h56

Bonjour

Ce que tu veux faire s'appelle un produit cartésien.
Tout simplement.
En clair: une multiplication.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Pour chaque élément du premier ensemble :
   Pour chaque élément du deuxième ensemble :
       Pour chaque élément du troisième ensemble :
            ...
                  Pour chaque élément du Kième ensemble :
                        Constuire un n-uplet.

Le code est déjà quasiment écrit.

Si tu ne veux pas faire de boucles imbriquées, il te faut garder les compteurs des dites boucles dans un while unique, et faire comme si elles l'étaient.
Plus long. Mais possible.

**BenkessiratAmina** · 30/01/2019, 23h03

Envoyé par tbc92

Ce n'est pas ça ? Pourtant tes données peuvent être représentées sous forme d'arbre, et le recensement de toutes les solutions, c'est la recherche de toutes les feuilles de l'arbre.

Sinon, pour avancer dans ton sens, Comment envisages-tu de stocker les données initiales ?
Dans ton premier message, tu disais cluster1=.... cluster2=... ce n'est pas exploitable, On va donc dire
cluster[1,1] = 1 ; cluster[1,3] = 2 ; cluster[1,3] = 3 ;
cluster[2,1] = 4 ; cluster[2,2] = 5 ;
cluster[3,1] = 6 ;
et
nb_clusters = 3
taille_cluster[1] = 3
taille_cluster[2] = 2
taille_cluster[3] = 1
s
Ok ?

Ok, Ok monsieur! je n'ai pas vu les choses ainsi, mais je valide

J'allais stocker les variables de mes cluster dans des vecteurs différents et c'est tout.
Je m'excuse pour la saturation de ma tête

Envoyé par Flodelarab

Bonjour

Ce que tu veux faire s'appelle un produit cartésien.
Tout simplement.
En clair: une multiplication.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Pour chaque élément du premier ensemble :
   Pour chaque élément du deuxième ensemble :
       Pour chaque élément du troisième ensemble :
            ...
                  Pour chaque élément du Kième ensemble :
                        Constuire un n-uplet.

Le code est déjà quasiment écrit.

Si tu ne veux pas faire de boucles imbriquées, il te faut garder les compteurs des dites boucles dans un while unique, et faire comme si elles l'étaient.
Plus long. Mais possible.

Je n'ai aucun problème de faire des boucles imbriquée. Je vais essayer le produit cartésiens et je reviendrai vers toi en cas de besoin

Ohhh Ohh dans ce cas je ne sais pas comment imbriquer mes boucles! vu que le nombre de boucle (ou de cluster) va être comme un paramétré! je ne connais donc pas le nombre exacte de boucle!! que faire??

**tbc92** · 31/01/2019, 09h48

Avec les notations précédentes, je pense qu'une procédure récursive comme celle-ci devrait être bonne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
fonction traite ( cluster, i1, i2, sch )
pour i = 1 a taille_cluster(i1)
  si i1 < i2 alors 
      call traite ( cluster, i1+1, i2, sch + "," + cluster[i1,i]
  sinon
      print ( sch)
  fin
fin

Et tu appelles cette fonction avec : call traite ( cluster, 1, nb_clusters , "")Je n'ai pas testé, il y a peut-être des bricoles à corriger.

La difficulté est effectivement que le nombre de niveaux est inconnu, mais avec cette procédure, ce n'est pas un problème.
Si tu as 500 ou 1000 niveaux, ça peut être un problème, et il faut envisager quelque chose de plus compliqué.

**Flodelarab** · 31/01/2019, 12h52

je ne connais donc pas le nombre exacte de boucle!!

Bien sûr que oui tu connais : c'est K !
Tu fais donc un tableau de K compteurs, tous mis à zéro. (probablement avec un autre tableau pour les maximum de chaque compteur.)

Tu fabriques un K-uplet.
Le compteur courant est le dernier.
Pour passer au cas suivant, tu incrémentes le compteur courant.
Si tu as passé le maximum, tu remets ce compteur à zéro et le compteur courant devient le précédent.
----S'il n'y a pas de compteur précédent. Tu as fais tous les cas possibles. (indice de compteur -1 si cet indice désigne réellement un compteur entre 0 et K-1) FIN !
----Sinon tu retournes à l'étape 3.
Sinon tu retournes à l'étape 1.

**Trap D** · 04/02/2019, 09h20

C'est la que l'on voit la puissance de Prolog :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
toutes_les_combinaisons(In, Out) :-
    setof(Comb, maplist(member, Comb, In), Out).

Par exemple :

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
?- toutes_les_combinaisons( [[1,2,3], [4,5], [6,7,8,9]], Out), maplist(writeln, Out).
[1,4,6]
[1,4,7]
[1,4,8]
[1,4,9]
[1,5,6]
[1,5,7]
[1,5,8]
[1,5,9]
[2,4,6]
[2,4,7]
[2,4,8]
[2,4,9]
[2,5,6]
[2,5,7]
[2,5,8]
[2,5,9]
[3,4,6]
[3,4,7]
[3,4,8]
[3,4,9]
[3,5,6]
[3,5,7]
[3,5,8]
[3,5,9]

**Flodelarab** · 04/02/2019, 10h45

Oui mais ça, ce n'est pas une réponse algorithmique. C'est une réponse de langage.

En python : (console interactive)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
>>> [[x,y,z] for x in [1,2,3] for y in [4,5] for z in [6,7,8,9]]
[[1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 6], [1, 5, 7], [1, 5, 8], [1, 5, 9], [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 6], [2, 5, 7], [2, 5, 8], [2, 5, 9], [3, 4, 6], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 5, 6], [3, 5, 7], [3, 5, 8], [3, 5, 9]]

**Trap D** · 04/02/2019, 10h57

Oui, mais j'aurai préféré que tu écrives un code pour n'importe quelle configuration des clusters, ç'aurait été plus convaincant (je ne doute évidemment pas que tu puisses le faire

)
Pour l'algo tu l'as déjà expliqué !

**BenkessiratAmina** · 04/02/2019, 19h07

Envoyé par Flodelarab

Oui mais ça, ce n'est pas une réponse algorithmique. C'est une réponse de langage.

En python : (console interactive)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
>>> [[x,y,z] for x in [1,2,3] for y in [4,5] for z in [6,7,8,9]]
[[1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 6], [1, 5, 7], [1, 5, 8], [1, 5, 9], [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 6], [2, 5, 7], [2, 5, 8], [2, 5, 9], [3, 4, 6], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 5, 6], [3, 5, 7], [3, 5, 8], [3, 5, 9]]

Je ne sais tjs pas comment gerer mes K clusters

**BenkessiratAmina** · 04/02/2019, 19h08

Envoyé par Trap D

C'est la que l'on voit la puissance de Prolog :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
toutes_les_combinaisons(In, Out) :-
    setof(Comb, maplist(member, Comb, In), Out).

Par exemple :

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
?- toutes_les_combinaisons( [[1,2,3], [4,5], [6,7,8,9]], Out), maplist(writeln, Out).
[1,4,6]
[1,4,7]
[1,4,8]
[1,4,9]
[1,5,6]
[1,5,7]
[1,5,8]
[1,5,9]
[2,4,6]
[2,4,7]
[2,4,8]
[2,4,9]
[2,5,6]
[2,5,7]
[2,5,8]
[2,5,9]
[3,4,6]
[3,4,7]
[3,4,8]
[3,4,9]
[3,5,6]
[3,5,7]
[3,5,8]
[3,5,9]