Générer toutes les substitutions d'une arraylist avec une autreRésolu

Question

Bonjour à tous.

Je suis étudiant en informatique et je rencontre des difficultés sur une partie d'un projet en Java (non noté je précise).

Je souhaiterais simplement arriver à finir et à comprendre le projet mais je bloque sur la partie suivante : 

J'ai deux listes (ArrayList) : l'une contenant des variables (x,y,z) par exemple et une autre contenant des constantes (A,B,C) par exemple.

Mon objectif est de créer toutes les substitutions possibles entre ces deux listes. Une substitution est un ensemble de couples.

voici un exemple : 

ArrayList de variables contenant : x,y
ArrayList de constantes contenant : A,B,C

Je veux obtenir les substitutions suivantes : 

x,A y,A (ceci est une substitutions contenant deux couples x,A et y,A)
x,A y,B
x,A y,C
x,B, y,A
x,B y,B
x,B y,C
x,C y,A
x,C y,B
x,C y,C

x,A signifiant x est remplacé par A; même chose avec y

Voici le code que j'essaie de faire fonctionner mais sans succès : 

public void Generer()
{
Iterator iConst = lConst.iterator(); // Iterator sur ma liste de constantes
Terme constante; // une constante

while(iConst.hasNext())// Tant que j'ai des constantes
{
constante = (Terme)iConst.next(); // on récupère la prochaine constante de la liste
for(int i=0;i<lVar.size();i++) // pour chaque variable
{
System.out.println("Couple : "+lVar.get(i)+","+constante);
// j'ai le couple variable courante/constante
}
}
}
Le problème c'est que ça me retourne avec l'exemple donné : 
x,A y,A
x,B y,B
x,C y,C

Et je ne vois pas comment répondre à mon problème. J'ai bien pensé à une méthode récursive mais là aussi je bloque.

Merci de m'aider. En espérant avoir été clair.

cs_GodConan · Accepted Answer

Tu as fais plusieurs erreur : la liste doit etre repasser en entier, toi tu la vides en suite c est quoi cette methode ;o) "GenererAllRec" bon je viens de te faire un exemple ;o) et cette foie je l ai testé compilé ;o) et vérifier ;o) ... ca correspond exactement à ce que je t ai montré ;o) donc inspire t en ;o) refait donc ton prog selon ce modéle si il te convient ;o) (en esperant que ce soit ca) ;o) héhé ;o) : import java.util.ArrayList; import java.util.Collections; /** * * @author GodConan */ public class Substitution { Object[] vars = {"x","y","z"}; Object[] values = {"A","B","C"}; int count = 0; public static void main(String[] args) { new Substitution().compute(); } public Substitution() {} public void compute() { try { ArrayList listeCouples = new ArrayList(); findLists( listeCouples, 0 ); System.out.println(" --- fin --- avec " + count + " resultats " ); } catch ( Exception e ) { System.out.println("Erreur :" + e); } } public void findLists( ArrayList liste, int idx ) { for ( int i = 0; i < values.length; i++ ) { ArrayList listeCouples = new ArrayList( liste ); listeCouples.add( new MonCouple(vars[idx], values[i]) ); if ( idx < ( vars.length - 1 ) ) findLists( listeCouples, idx + 1 ); else { count++; System.out.println( listeCouples.toString() ); } listeCouples.clear(); // ca sert pas vraiment :o) listeCouples = null; // ces 2 ligne sont la pour forcer le non réferencement des objets // normalement ca se fait tout seul ;o) } } public class MonCouple { Object var = null; Object value = null; MonCouple( Object var , Object value ) { this.var = var; this.value = value; } @Override public String toString() { return " ( " + var.toString() + " , " + value.toString() + " ) "; } } } évidement à la place du traitement je ne fait qu un System.out ;o) mais cela permet de vérifier que le resultat est bien : [ ( x , A ) , ( y , A ) , ( z , A ) ] [ ( x , A ) , ( y , A ) , ( z , B ) ] [ ( x , A ) , ( y , A ) , ( z , C ) ] [ ( x , A ) , ( y , B ) , ( z , A ) ] [ ( x , A ) , ( y , B ) , ( z , B ) ] [ ( x , A ) , ( y , B ) , ( z , C ) ] [ ( x , A ) , ( y , C ) , ( z , A ) ] [ ( x , A ) , ( y , C ) , ( z , B ) ] [ ( x , A ) , ( y , C ) , ( z , C ) ] [ ( x , B ) , ( y , A ) , ( z , A ) ] [ ( x , B ) , ( y , A ) , ( z , B ) ] [ ( x , B ) , ( y , A ) , ( z , C ) ] [ ( x , B ) , ( y , B ) , ( z , A ) ] [ ( x , B ) , ( y , B ) , ( z , B ) ] [ ( x , B ) , ( y , B ) , ( z , C ) ] [ ( x , B ) , ( y , C ) , ( z , A ) ] [ ( x , B ) , ( y , C ) , ( z , B ) ] [ ( x , B ) , ( y , C ) , ( z , C ) ] [ ( x , C ) , ( y , A ) , ( z , A ) ] [ ( x , C ) , ( y , A ) , ( z , B ) ] [ ( x , C ) , ( y , A ) , ( z , C ) ] [ ( x , C ) , ( y , B ) , ( z , A ) ] [ ( x , C ) , ( y , B ) , ( z , B ) ] [ ( x , C ) , ( y , B ) , ( z , C ) ] [ ( x , C ) , ( y , C ) , ( z , A ) ] [ ( x , C ) , ( y , C ) , ( z , B ) ] [ ( x , C ) , ( y , C ) , ( z , C ) ] --- fin --- avec 27 resultats ;o) soit exactement ce que tu attendais !! non?? GodConan ;o)

cs_GodConan · Answer

Salut ;o) 

au vu de ton résultat ;o) tu devrais voir (comme par hazard ;o) ) que tu as 3 fois moins de réponse que prévu ;o) et uniquement des réponses bien précises ;o) 

en fait il te faut les combinaisons pour chaque variable de toute les constantes ;o) donc il te faut scanner 2 fois tes constantes : 



for( Terme constX : lConst )
{
for( Terme constY : lConst )
{
//for(int i=0;i<lVar.size();i++) // pour chaque variable 
{
System.out.println("Couple : "+lVar.get(0)+","+constX);
System.out.print(" "+lVar.get(1)+","+constY);
}
}
}

Evidemant cette exemple  ;o) ne fonctionne que pour 2 variables ;o)
pour plus c est un peu moins simple ;o) 
et surtout tu n est pas tres clair sur le résultat attendu !! 

GodConan ;o)

shadowxx011 · Answer

Tout d'abord merci pour cette réponse.

Je vais essayé d'être un peu plus clair dans le résultat attendu.

J'ai deux arraylist : une contenant toutes mes variables (par exemple x,y) et une autre liste contenant que des constantes (par exemple poire, pomme et abricot)

Mon objectif est d'arrivé à générer toutes les combinaisons tels qu'on puisse dire : quand x prends la valeur poire, y peut valoir poire,pomme ou abricot. C'est ce que j'appelle une substitution. Dans mon exemple on a donc les substitutions suivantes : 

x,poire y,poire (quand x vaut poire, y peut valoir poire : c'est une substitution)
x,poire y,pomme( la valeur de x ne change pas mais celle de y peut changer)
x,poire y,abricot

x,pomme y,poire (ici on a générer toutes les substitutions avec x,poire donc la constante associée à x change)
x,pomme y,pomme
x,pomme y,abricot

Enfin ,on résonne de la même façon avec x,abricot

x,abricot y,poire
x,abricot y,pomme
x,abricot y,abricot

Et je cherche à générer toutes ces substitutions 1 à 1 pour les stocker dans une nouvelle liste contenant des substitutions. En gros j'aurais : 

//ici on a x vaut poire, y vaut poire; on ajoute les couples (x,poire), (y,poire) à la liste de substitution (listeSubstitutions.add(new Substitution((x,poire),(y,poire))

Et on fait ça pour chaque substitution.

Mais je n'arrive pas à généraliser l'idée pour que ça fonctionne quel que soit le nombre de variables et de constantes.

J'espère avoir été un peu plus clair.

Merci

cs_GodConan · Answer

;o) ok 
donc mon exemple fonctionne bien pour 2 variables et N constantes  ;o)  
le résonnement est asser basic en fait ;o) tu vois bien qu il te faut pour obtenir le résutat voulu que tu parcours 'n' fois la liste de tes constantes avec n étant ton nombre de variable ;o) 

donc cela te fait faire ;o) un nombre inconu (ou plutot variant) d'itérations consécutives ;o)

donc  ;o) si pour toutes variables assignées tu dois prévoir tout les cas possible ;o) et donc ton but n est plus d obtenir des couples mais bien des 'tuples' ?  ;o) 

je te propose ca :

{
List couples = new List(); 
findList( couples, 0);
}

void findList( couples, int i )
{
For ( Term const : lConst )
{
  List couples = new List( couples ); 
  couples.add( lVar.get(i), const );
  if ( i < (lVar.size -1))
    findList( couples, i+1 );
  else
    {
// ben on est arrivé au bout d une serie de couple c est donc la que   
// tu fais ce que tu as a faire sur ta liste de couple
//un truc du genre :
listeSubstitutions.add(new Substitution(couples));

    }
  couples.dispose(); couples = null;
}
}

ici le raisonnement récussif est pris à l envers ;o), habituellement on le fait plutot sur des méthodes "get" ;o) ce que tu peux faire pour obtenir une liste de liste de liste.... ;o) avec n dimention n etant le nombre de variable ;o) 

tu te rend bien compte que si ton nombre de variable est suffisement grand ;o) tu exploses la memoire ou la stack ;o) ... (trés grand quand meme) ;o) 

PS : j ai fait ca au pied levé ;o) cela ne ce compile surement pas ;o) mais c est l idée ;o) ... 

GodConan ;o)

shadowxx011 · Answer

Tout d'abord, merci. Cette explication a déjà clarifiée quelques trucs. Cependant, je n'arrive pas à obtenir le résultat escompté en me basant sur ta méthode. Voilà ce que j'ai fait : (en Java) 1 méthode Generer: public void Generer() { ArrayList alTerme = new ArrayList // On créer une nouvelle AL de CoupleTerme (1 couple de terme c'est par exemple (x,poire)) GenererRecursif(alTerme,0) // appel à la méthode récursive } public void GenererRecursif(ArrayList couples, int i) { for(int j=0;j lcouples = new ArrayList(); // 1 seconde liste de couple de termes lcouples.add(new CoupleTermes(lVar.get(i), lConst.get(j))); // j'ajoute à cette liste le couple (variable courante, constante courante) System.out.println("Couple "+lVar.get(i)+","+lConst.get(j)); // EN FAIT, ICI LE BUT EST D'AVOIR UNE LISTE DE SUBSTITUTION lcouples contiendrait alors par exemple (x,poire)(y,poire)(z,poire) if ( i<(lVar.size()-1)) GenererAllRec(couples,i+1); // appel récursif else { // ben on est arrivé au bout d une serie de couple c est donc la que // tu fais ce que tu as a faire sur ta liste de couple //un truc du genre : // ICI ON A GENERER UNE SUBSTITUTION A PART ENTIERE ( on a donc trois couples dans lcouples pour mon exemple (x,poire)(y,poire)(z,poire) // ON AJOUTE ALORS CETTE SUBSTITUTION COMPLETE A UNE LISTE DE SUBSTITUTION listeSubstitutions.add(new Substitution(lcouples)); //ICI on a ajouté à listeSubstitutions la liste [(x,poire)(y,poire(z,poire)] //PUIS, on recommencera avec la liste [(x,poire)(y,poire),(z,pomme)] //Puis avec [(x,poire)(y,poire),(z,abricot)]; puis [(x,poire)(y,pomme),(z,poire)], etc... } couples = null; // ça je ne vois pas trop à quoi ça sert) } } // Le problème c'est que avec cet algo, je n'ai pas lcouples qui contient mes 3 couples de termes (x,poire)(y,poire)(z,poire) mais uniquement un seul des 3. J'espère que mon explication est assez claire et que tu pourras m'aider. Merci

cs_GodConan · Answer

met des balise de code java STP c est chiant à lire

GodConan ;o)

shadowxx011 · Answer

Comment ça ? c'est écrit en Java.

shadowxx011 · Answer

Ok j'ai compris :) public void Generer() { ArrayList alTerme = new ArrayList // On créer une nouvelle AL de CoupleTerme (1 couple de terme c'est par exemple (x,poire)) GenererRecursif(alTerme,0) // appel à la méthode récursive } public void GenererRecursif(ArrayList couples, int i) { for(int j=0;j lcouples = new ArrayList(); // 1 seconde liste de couple de termes lcouples.add(new CoupleTermes(lVar.get(i), lConst.get(j))); // j'ajoute à cette liste le couple (variable courante, constante courante) System.out.println("Couple "+lVar.get(i)+","+lConst.get(j)); // EN FAIT, ICI LE BUT EST D'AVOIR UNE LISTE DE SUBSTITUTION lcouples contiendrait alors par exemple (x,poire)(y,poire)(z,poire) if ( i<(lVar.size()-1)) GenererAllRec(couples,i+1); // appel récursif else { // ben on est arrivé au bout d une serie de couple c est donc la que // tu fais ce que tu as a faire sur ta liste de couple //un truc du genre : // ICI ON A GENERER UNE SUBSTITUTION A PART ENTIERE ( on a donc trois couples dans lcouples pour mon exemple (x,poire)(y,poire)(z,poire) // ON AJOUTE ALORS CETTE SUBSTITUTION COMPLETE A UNE LISTE DE SUBSTITUTION listeSubstitutions.add(new Substitution(lcouples)); //ICI on a ajouté à listeSubstitutions la liste [(x,poire)(y,poire(z,poire)] //PUIS, on recommencera avec la liste [(x,poire)(y,poire),(z,pomme)] //Puis avec [(x,poire)(y,poire),(z,abricot)]; puis [(x,poire)(y,pomme),(z,poire)], etc... } couples = null; // ça je ne vois pas trop à quoi ça sert) } } // Le problème c'est que avec cet algo, je n'ai pas lcouples qui contient mes 3 couples de termes (x,poire)(y,poire)(z,poire) mais uniquement un seul des 3.

shadowxx011 · Answer

Alors que dire si ce n'est un GRAND MERCI !

Grâce à ton code et tes explications j'ai tout compris et j'ai un programme 100% fonctionnel.

Mais l'essentiel c'est d'avoir compris.

Encore merci.

Ps : Comment je fais pour passer le sujet en "résolu" ? :)

cs_GodConan · Answer

;o) y a pas à dire t es en veine ;o) ... 
j ai pas trop l habitude de fournir des exemples ;o) ... héhé ;o) 

l essentiel etant que tu ais compris... les méthodes récursives s'utilisent asser réguliérement ;o) en prog ;o) 

Bonne prog, ++

GodConan ;o)

Générer toutes les substitutions d'une arraylist avec une autre

10 réponses

Votre réponse