Comment Obtenir toutes les combiniaisons possibles [Résolu]

Signaler
Messages postés
57
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
17 mars 2015
-
Messages postés
57
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
17 mars 2015
-
Bonjour tout le monde ;

J'ai un problème dans le calcul des combinaisons possibles. Prenant cet exemple :
X1 = {(1), (1,2)}
X2 = {(2), (1,2)}
X3 = {(3),(3,4,5)}
X4 = {(4), (4,5)}
X5 = {(4,5)}

Je dois calculer les combinaisons possibles de tous les ensembles sauf un ensemble, par exemple :
toutes les combinaisons des ensembles X2, X3, X4, X5. Dans ce cas on a 8 combinaisons :
1) {(2),(3),(4),(4,5)}
2) {(2),(3),(4,5),(4,5)}
3) {(2),(3,4,5),(4),(4,5)}
4) {(2),(3,4,5),(4,5),(4,5)}
5) {(1,2),(3),(4),(4,5)}
6) {(1,2),(3),(4,5),(4,5)}
7) {(1,2),(3,4,5),(4),(4,5)}
8) {(1,2),(3,4,5),(4,5),(4,5)}

est ce quelqu'un peut me dire comment faire ça en java ? j'ai essayé de programmer mais j'ai pas réussi !!
merci d'avance.

6 réponses

Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
25
Salut,

Au niveau de l'algorithme tu es bien parti mais il ne faut pas réinitialiser la liste après chaque appel récursif ! Il faut seulement enlever le dernier élément ajouté.

Je te suggère de remplacer :
ArrayList> list

par :
Stack<List> stack


Puis de remplacer :
list.add(PlayerCoalitions.get(index).Coalitions.get(j));

par :
stack.push(PlayerCoalitions.get(index).Coalitions.get(j));


Et enfin :
if(index > = PlayerCoalitions.size() ){
  this.Combinaison.add(list);	
 }

par :
else {
combinaison.add(new ArrayList<List>(stack));
}


Par ailleurs, je remarque que tu n'utilises pas les interfaces quand c'est possible, tu n'utilises pas les concepts objets et pas non plus les conventions de nommage habituelles.
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
25
J'oubliais le principal,

remplacer :
list = new ArrayList>();

par :
stack.pop();
Messages postés
6414
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
29 juillet 2020
340
Salut,

Qu'as tu fait ? Et qu'est ce qui te bloque ?
Messages postés
57
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
17 mars 2015

Salut;
voilà mon programme, j'ai essayé de le resoudre sous forme d'une fonction récursive :
public class MemberCoalitions {
public int Id; // player
public ArrayList> Coalitions = new ArrayList>();
}

public class test {
public ArrayList>> Combinaison= new ArrayList>>();
public void generer (ArrayList> list, int index, ArrayList<MemberCoalitions> PlayerCoalitions){
 index = index +1;
 if(index < PlayerCoalitions.size()){
 for(int j =0; j< PlayerCoalitions.get(index).Coalitions.size(); j++){
  list.add(PlayerCoalitions.get(index).Coalitions.get(j));
  generer (list, index, PlayerCoalitions);
  list = new ArrayList>();
 }
}
 if(index > = PlayerCoalitions.size() ){
  this.Combinaison.add(list);	
 }	
}



Mon exemple est comme suit :
PlayerCoalitions[0]= {(2), (1,2)}
PlayerCoalitions[1]= {(3), (3,4)}
PlayerCoalitions[2]= {(4), (4,5)}

je dois obtenir 8 combinaisons entre les éléments des différents ensembles. Le résultat est le suivant :
Combinaison[0]={(2),(3),(4)}
Combinaison[1]={(2),(3,4),(4)}
Combinaison[2]={(2),(3),(4,5)}
Combinaison[3]={(2),(3,4),(4,5)}
Combinaison[4]={(1,2),(3),(4)}
Combinaison[5]={(1,2),(3),(4,5)}
Combinaison[6]={(1,2),(3,4),(4)}
Combinaison[7]={(1,2),(3,4),(4,5)}

Mais mon programme me donne le résultat suivant :

[[2], [3], [4]]
[[4, 5]] // il manque [2], [3]
[[3, 4], [4]] // il manque [2]
[[4, 5]]// il manque [2], [3,4]
[[1, 2], [3], [4]]
[[4, 5]] // il manque [1,2], [3]
[[3, 4], [4]] // il manque [1,2]
[[4, 5]] // il manque [1,2], [3,4]

J'ai remarqué que les meme éléments qui appertiennent à deux combinaisons différentes sont supprimé et reste que les élement différents comme expliquer dans le résultat ci-dessus.
J'éspére que vous avez compris mon probléme, meci d'avance.
Messages postés
57
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
17 mars 2015

Merci bcp jojolemariole, il marche maintenant. Concernant tes remarques, oui t'as raison, puisque je suis débutante en java.
Messages postés
57
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
17 mars 2015

Bonjour;

Je veux savoir est ce que je peux écrire ce programme sous forme séquentielle. Vue le grand nombre de combinaisons, j'obtiens une exception de dépassement de mémoire. Je veux par exemple; afficher combinaison par combinaison sans les conserver dans une liste mais je dois changer le code, il doit s'ecrit d'une façon séquentielle non sous forme d'une fonction récursive.
J'ai vraiment besoin de la réponse. Merci d'avance.