Boucle imbriquées ?

Version imprimable

28/09/2006, 12h50
ptr83

Boucle imbriquées ?

Je cherche a faire une fonction qui renvoie dans l'ordre les produits de substitutions d'un produit qu'on lui envoie.

Par exemple:
Le produit NA a comme produits de substitutions les produits NB, NC, ND et NE
Le produit NC a comme produits de substitutions les produits NB, NE, NF, NG et NI
Le produit NF a comme produits de substitutions les produits NC, NH, NI et NJ
Le produit NI a comme produits de substitutions les produits NL, NM et NN.
Les produits NB, ND, NE,etc n'ont pas de substitu.

Ce que je veux c'est qu'a chaque fois que la fonction trouve un subsitu elle aie vérifier si ce produit n'a pas lui aussi des produits de substitutions.

Et donc la réponse dans mon exemple si l'on envoie NA a la fonction serait : NB (qui n'a pas de produit de subsitution on passe donc au produit de substitution suivant de NA), NC (qui lui a des substitu donc on les liste avant de continuer les autres subsituts de NA), (on passe le premier substitu de NC qui est B car il a déjà été listé) NE, NF(qui a des substitut donc on les liste avant de finir NC et ainsi de suite), NH, NI, NL, NM, NN, NJ, NG, ND...

J'arrive a prendre les substituts si je connais jusqu'a quel degré je dois aller hors je ne le connais pas...

Si quelqu'un peut m éclairer: un grand MERCI.
28/09/2006, 13h20
davcha

Tu dois utiliser la récursivité, mais prends garde aux cycles, parce que dans ton système de substitus, tu as très probablement des cycles.

Salut,

Je pense aussi que dans ton cas vaut mieux faire un algo récursif.
Imaginons que ta fonction qui fait le calcul à comme signature ProduitSubs(Produit p, listeDeProduit lp)
Le code de la fonction pourrai être de la forme suivante en pseudo algorithme(Vérifie l'algo avant de l'implémenter 8-) ) :
Code:

1 2 3 4 5 6 7 ListeProduit produits = rechercheSubstitutionProduit(p); Si produits vide alors ajouter p a la liste lp sinon pour chaque Produit ptmp de ta liste de produit Ajouter résultat de ProduitSubs(ptmp) dans la liste lp fin pour fin si
Pour commencer le calcul tu passes à la fonction un produit et une liste vide.
A la fin de ta fonction tu auras la liste des substituts de ton produit.
Attention comme indiqué par davcha il ne faut pas avoir de cycle sinon le code boucle indéfiniment.

Tout d'abbord merci pour votre intéret à mon problemes et vos réponses.

Mais j'avoue que j'ai du mal... voici le code que j'ai fait suivant vos explications:

Code:

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
 public Stack GetMainSubstitutes(int iin){
		    Stack AnswerStack = new Stack();
 
	        //get main substitues
	        Session session = HibernateUtil.getSessionFactory().openSession();
			List result = null;
			session.beginTransaction();
 
			result  = session.createQuery("from ArtSub where iin= ?")
			.setInteger(0,iin).list();
			session.getTransaction().commit();
			session.close();
 
			if (result.size()>0) {
			    for(int i=0; i<result.size(); i++){
			        ArtSub as = (ArtSub)result.get(i);
					AnswerStack.push(new Integer(as.getSub()));
			    }
			}	
			return AnswerStack;
	 }
 
	public GetSubstitutes(int p, Stack lp) {
	    Stack produits = GetMainSubstitutes(p);
	    if(produits.empty()){
	        lp.push(new Integer(p));
	    }else{
	        while(!produits.empty()){
	            Integer iin2 = (Integer) produits.pop();
	            lp.push(new Integer(GetSubstitutes(iin2,lp)));
	        }
	    }

J'ai mal compris quelque chose?
Et plus particulièrement, "Ajouter résultat de ProduitSubs(ptmp) dans la liste lp" le resultat de ProduitSubs c'est quoi? la liste lp??

J'ai fait l'algo un peu vite, c'était juste pour donner une idée.
Si j'ai bien compris tes produits sont des entiers.
J'écrirait la méthode getSubstitute de cette façons (vérifie la ;) )
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public void getSubstitutes(int p, Stack lp) { Stack produits = getMainSubstitutes(p); if (produits.empty()) { //p n'a pas de substitue donc on l'ajoute à la pile lp.push(new Integer(p)); } else { while (!produits.empty()) { Integer iin2 = (Integer) produits.pop(); getSubstitutes(iin2, lp); } } }
Pourquoi utilise tu une pile au lieu d'une liste?
Sinon par convention les noms de méthode commence par des minuscules.
Autre conseil pour ta méthode getMainSubstitutes il faudrait mettre en place un système de cache pour éviter de faire à chaque fois une requête sur ta base de donnée.

28/09/2006, 15h54
ptr83

MErci

tu conseillerais quel type de liste alors?
28/09/2006, 16h00
hydraland

Je conseillerai une ArrayList.
29/09/2006, 14h49
ptr83

Ok encore merci

et pour les cycles alors, que faire?
29/09/2006, 16h29
hydraland

1 pièce(s) jointe(s)

Détecter les cycles n'est pas très évident. Si on voit ton système comme un arbre, alors si un neud possède les mêmes fils qu'un noeud parent alors tu à un cycles. Cf une image pour être plus clair ;)
Pièce jointe 5251
29/09/2006, 16h39
millie

Citation:

Envoyé par hydraland

Détecter les cycles n'est pas très évident. Si on voit ton système comme un arbre, alors si un neud possède les mêmes fils qu'un noeud parent alors tu à un cycles. Cf une image pour être plus clair ;)
Pièce jointe 5251

Tu parles d'arbre alors qu'un arbre est un graphe connexe ACYCLIQUE. Donc forcement, il peut pas y avoir de cycle dans un arbre.
30/09/2006, 12h31
mathk

Ce que tu cherche c'est un algorithme de la fermeture transitive.
Cherche sur google
02/10/2006, 11h07
ptr83

Ce que vous apellez un cycle c'est (un exemple suimple):
Article 1 a comme substitut les articles 2 et 3
L'article 2 a comme substitut l'article 1

Et donc le risque c'est que cela boucle éternellement en allant de l'article 1 à l'article 2 c'est ça?
Si oui c'est bon j'ai résolu ce problème...
Si c'est autre chose, là je ne saisis pas...

Quoiqu'il en soit merci pour tout et à tous pour votre aide.
02/10/2006, 11h11
millie

Citation:

Ce que vous apellez un cycle c'est (un exemple suimple):
Article 1 a comme substitut les articles 2 et 3
L'article 2 a comme substitut l'article 1

Oui, c'est parfaitement ça. Tu peux imaginer le schéma comme une carte routière avec des rues à sens unique, si tu peux revenir sur tes pas (sans prendre de sens interdit :P ), c'est qu'il y a un cycle.
02/10/2006, 14h28
siplusplus

1 pièce(s) jointe(s)

Bonjour,

Salut Ptr83,
Le problème est intéressant et pourrais-tu reformuler de manière différente ton problème. Car d'après ce que j'en comprends actuellement ce que tu obtiens est un pseudo arbre en graphe avec un boucle entre NC et NF et je suppose que c'est cette relation qui bouclerait indéfiniment mais ne serait pas une imbrication de boucle.
Même avec un algorithme de système expert d'ordre 0 il y aura toujours cette barrière NC/NF.
Le dessin suivant m'a permis de détecter le cycle en question.

Pièce jointe 5320
02/10/2006, 16h00
ptr83

Le problème des cycles est résolu en fait je fais juste une petite vérification avant mon appel récursif :

Si l'article fait déjà partie de la liste de substitut que je construis, je ne fait pas de nouvel appel.

JE pense que c'est bon comme cela... Merci.