Comment Obtenir toutes les combiniaisons possibles [Résolu]

ImFaith 57 Messages postés dimanche 6 décembre 2009Date d'inscription 17 mars 2015 Dernière intervention - 20 nov. 2012 à 19:30 - Dernière réponse : ImFaith 57 Messages postés dimanche 6 décembre 2009Date d'inscription 17 mars 2015 Dernière intervention
- 21 déc. 2012 à 17:01
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.
Afficher la suite 

6 réponses

Répondre au sujet
cs_jojolemariole 519 Messages postés mercredi 21 mars 2007Date d'inscription 19 décembre 2016 Dernière intervention - 21 nov. 2012 à 14:47
+3
Utile
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.
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de cs_jojolemariole
cs_jojolemariole 519 Messages postés mercredi 21 mars 2007Date d'inscription 19 décembre 2016 Dernière intervention - 21 nov. 2012 à 14:48
+3
Utile
J'oubliais le principal,

remplacer :
list = new ArrayList>();

par :
stack.pop();
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de cs_jojolemariole
cs_Julien39 6449 Messages postés mardi 8 mars 2005Date d'inscription 15 mars 2018 Dernière intervention - 21 nov. 2012 à 10:01
0
Utile
Salut,

Qu'as tu fait ? Et qu'est ce qui te bloque ?
Commenter la réponse de cs_Julien39
ImFaith 57 Messages postés dimanche 6 décembre 2009Date d'inscription 17 mars 2015 Dernière intervention - 21 nov. 2012 à 10:39
0
Utile
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.
Commenter la réponse de ImFaith
ImFaith 57 Messages postés dimanche 6 décembre 2009Date d'inscription 17 mars 2015 Dernière intervention - 21 nov. 2012 à 15:56
0
Utile
Merci bcp jojolemariole, il marche maintenant. Concernant tes remarques, oui t'as raison, puisque je suis débutante en java.
Commenter la réponse de ImFaith
ImFaith 57 Messages postés dimanche 6 décembre 2009Date d'inscription 17 mars 2015 Dernière intervention - 21 déc. 2012 à 17:01
0
Utile
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.
Commenter la réponse de ImFaith

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.