Bonjour,
ca fait 2 ou 3 jours que je bloque sur un probleme de combinaisons, je cherche a faire un outil de poker qui calculera quelques proba, et lorsque j'essaye de lister toute les combinaisons de cartes possibles (sans ordre et sans répétitions) je tombe sur des valeurs erronées:
on sait qu'il existe au texas holdem 52!/(7!*(52-7)!) mains de 7 cartes differentes, soit 133 784 560 combinaisons differentes
cependant je n'arrive pas a trouver d'algorithmes pour lister toute ces combinaisons sans répétitions (par exemple 2 3 AS 8 9 V D c'est pareil que 3 2 AS 8 9 V D)
Pour commencer, tu peux créer un objet carte, il y a deux paramètres (au moins) valeur et couleur (par exemple dame de pique) tu peux créer des enum pour te faciliter les choses.
Et il faut surtout réimlémenter la méthode equals() et retourner vrai si valeur et couleur sont les mêmes.
Ensuite, tu peux créer une classe paquet de cartes, qui est un exends d'aRrayList<Carte> qui te servira à distribuer ...
Et enfin, j'en viens à la résolution de ton problème, tu créé une classe main qui contient un tableau ou une arrayList de 7 cartes et là, tu réimplémentes la fonction equals pour ton objet Main la fonction retourne vrai seulement si toutes les cartes sont identiques.
Et c'est cette derniere fonction qui va te permettre de supprimer les doublons.
Je pense que tu devrais plutôt créer un algorithme dédié pour chaque type de combinaison.
Exemple : j'ai le sept de pic et le sept de coeur. Le sept de trèfle est arrivé au flop, j'ai donc 2 chances sur 47 de toucher mon carré.
Tu peux faire un raisonnement similaire pour toutes les combinaisons.
Cependant, si tu ne veux pas faire ça, tu peux effectivement chercher toutes les combinaisons possibles comportant les 2 cartes que tu as en main et ainsi obtenir les probabilités. Avec un ordinateur actuel, ce n'est pas du tout un gros problème : 5 cartes parmi 50 = 50! / ( 5! * 45! ) soit un peu plus de 2 millions de combinaisons possibles. C'est pas la mer à boire.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
/**
*
* @author guehenneux
*
*/
public class TestPoker {
public static int nombreCombinaisons;
public static void main(String[] args) {
/*
* liste des cartes initiales
*/
List cartes = new ArrayList();
for (int carte = 0; carte < 52; carte++) {
cartes.add(carte);
}
/*
* on en prend 2 au hasard
*/
Random random = new Random();
int carte0 = cartes.remove(random.nextInt(cartes.size()));
int carte1 = cartes.remove(random.nextInt(cartes.size()));
/*
* on constitue la main initiale avec ces deux cartes
*/
LinkedList main = new LinkedList();
main.add(carte0);
main.add(carte1);
/*
* on teste toutes les combinaisons possibles a partir de cette main
* initiale
*/
testerCombinaisons(main, cartes, 0);
}
/**
*
* @param cartesEnMain
* @param cartesRestantes
* @param indexChoix
*/
public static final void testerCombinaisons(
LinkedList combinaison, List cartesRestantes,
int indexChoix) {
int nombreCartesCombinaison = combinaison.size();
int nombreCartesRestantes = cartesRestantes.size();
if (nombreCartesCombinaison == 7) {
/*
* on a une combinaison complete : on la traite (ici, je me contente
* de l'afficher)
*/
nombreCombinaisons++;
} else {
/*
* la combinaison est encore incomplete, on doit rajouter une carte
* avant de la tester a nouveau
*/
int carteRestante;
/*
* on teste avec chacune des cartes restantes
*/
for (int indexCarteRestante = indexChoix; indexCarteRestante < nombreCartesRestantes; indexCarteRestante++) {
carteRestante = cartesRestantes.remove(indexCarteRestante);
/*
* on ajoute la carte restante choisie a la combinaison
*/
combinaison.addLast(carteRestante);
/*
* on teste toutes les combinaisons incluant cette carte
*/
testerCombinaisons(combinaison, cartesRestantes,
indexCarteRestante);
/*
* puis on retire la carte afin d'en essayer une autre (on
* n'oublie pas de reintegrer la carte aux cartes restantes)
*/
combinaison.removeLast();
cartesRestantes.add(indexCarteRestante, carteRestante);
}
}
}
}
En même temps, pour calculer les probabilités, tu n'as pas besoin de connaitre toutes les combinaisons, il suffit de savoir quelles cartes permettent de dépasser une main donnée et de calculer la probabilité d'avoir ces cartes. Et le tour est joué, lister toutes les mains, ca va prendre un temps fou...
j'ai déja crée une classe carte avec fonction equal, j'ai également crée une classe deck qui est une liste de cartes.
je me sert egalement d'une classe main qui represente une liste de 2 cartes, et lorsque la main est selectionnée ca retire les cartes du deck.
j'ai déja pensé a la solution que tu proposes seulement ca prend deja un temps fou a lister toute les combiaisons avec doublons (arrangements), alors repasser ce résultat dans une autre fonction pour éliminer les doublons va prendre d'autant plus de temps... (pour info mon algo met deja 50 sec pour lister les combinaisons avec arrangements en plus)
le petit logiciel que j'essaye de faire va calculer toute sortes de proba, dont les probas de toucher tel ou tel tirage en fonction d'une main selectionnée, par exemple quel est la proba de toucher un carré avec une paire en main...
j'essaye donc de trouver un algo qui me donnera toute les combinaisons directement (sans les arrangements), je pense que cela est possible grace a un algo récursif, mais je n'ai toujours pas trouvé (pas faute d'avoir cherché :p)
si je n'y arrive pas je n'aurais pas d'autres choix que d'utiliser la methode que tu proposes, mais pour des questions de performances ca va vraiment devenir embetant :/
merci cependant de t'etre penché sur mon probleme, mais je reste en attente d'une solution miracle (si elle existe !)
Cela fait un bon moment que j'essaie de trouver une réponse à mon problème mais rien à faire. Je me permet de s’adresser à vous pour une aide.
J'ai un ensemble de nombre E ={1,2,3,4} et je veux avoir toutes les solutions permettant de diviser E en sous ensembles.
Par exemple pour 3 nombres les sous ensembles sont:
{1,2,3}
{1}, {2,3}
{1,2},{3}
{1,3},{2}
{1},{2},{3}
Pour 4 nombre c'est plus compliqué car on peut avoir plus de deux sous ensemble on a 3 sous ensembles pour chaque solution:
par exemple:
{1,2},{3,4}
{1,2},{3},{4}
{1},{2},{3,4}
Quelqu'un a une idée sur comment faire la récursion ?
