Comment Obtenir toutes les combiniaisons possiblesRésolu

Question

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.

cs_jojolemariole · Accepted Answer

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 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(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.

cs_Julien39 · Answer

Salut,

Qu'as tu fait ? Et qu'est ce qui te bloque ?

ImFaith · Answer

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 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.

cs_jojolemariole · Answer

J'oubliais le principal,

remplacer :
list = new ArrayList>();
par :
stack.pop();

ImFaith · Answer

Merci bcp jojolemariole, il marche maintenant. Concernant tes remarques, oui t'as raison, puisque je suis débutante en java.

ImFaith · Answer

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.

Comment Obtenir toutes les combiniaisons possibles

6 réponses

Votre réponse

Discussions similaires