Dénombrer
On demande souvent au lycée de faire des simulations et de tenter de bidouiller quelque chose avec deux ou trois résultats de statistique inférentielle admis ou « démontrés » par observation...
Nous allons plutôt rester dans un domaine mathématique non magique et ne plus faire un sondage sur des résutats partiels mais dénombrer tous les résultats.
Cela nous permettra de rester dans un domaine « démontrable » et non plus seulement « observable », mais aussi de faire quelques calculs et d'un point de vue programmation, d'être un peu confronté à des problèmes d'efficacité.
Nous allons pourtant utiliser un langage peu réputé pour sa vitesse, Python, mais largement utilisé et facile d'accès.
Nous verrons dans un deuxième temps une approche plus constructive en utilisant cette fois le langage Haskell.
Les itérateurs et l'évaluation paresseuse
Pour celles et ceux impliqués dans les options informatiques ISN en S ou SIN en STI2D, il peut être intéressant de faire découvrir un concept difficile mais largement utilisé dans les langages modernes, celui d'évaluation paresseuse. C'est une idée importante qui fait la force d'un langage comme Haskell et que Python a repris sous la forme des itérateurs. Leur rôle est même devenu prépondérant en Python 3.
Nous n'entrerons pas dans les détails, mais ce qui nous intéresse ici c'est, entre autre, qu'un itérateur pythonesque est évalué paresseusement, c'est-à-dire qu'on peut le créer sans forcément l'évaluer en entier ni tout de suite : c'est une sorte d'objet potentiellement évaluable. On peut prévoir des opérations sans les faire tout de suite mais on peut l'utiliser comme si ces opérations étaient faites : c'est en cela que l'évaluation est paresseuse. Cela permet d'avoir une meilleure gestion de la mémoire mais cela est un problème purement informatique. Revenons à notre mathématique...
Le Poker : un tour d'horizon de la mathématique discrète
Nous allons essayer de comptabiliser les différentes combinaisons du jeu de poker pour calculer la probabilité de les obtenir dans des conditions non truquées de jeu.
On traitera le cas d'un jeu de 32 cartes et celui d'un jeu de 52 cartes. Voici un petit rappel des différentes mains:
On rentre d'abord la liste des symboles et la liste des valeurs:
# Liste des symboles des cartes symboles = ['Trefle','Carreau','Coeur','Pique'] # Liste des valeurs dans un jeu de 32 cartes vals_32 = ['Sept','Huit','Neuf','Dix','Valet','Dame','Roi','As'] # Ensemble des valeurs dans un jeu de 52 cartes vals_52 = ['Deux','Trois','Quatre','Cinq','Six'] + vals_32
Il s'agit ensuite de créer l'ensemble de toutes les mains possibles de cinq cartes.
Il faut d'abord se demander comment on va modéliser une carte : choisissons par exemple de le faire sous forme d'un couple
Une première idée serait d'utiliser les listes par compréhension que l'on retrouve dans les langages de programmation modernes : Python, Haskell, Scala...mais aussi CarMetal.
[(valeur,couleur) for valeur in vals_32 for couleur in symboles]
Nous allons plutôt utiliser des outils présents dans la bibliothèque itertools qui, comme son nom l'indique, fournit des outils pour utiliser les itérateurs.
Il existe en particulier une fonction product(iter1,iter2) qui renvoie justement le produit de deux itérateurs. On en profite pour créer une fonction qui fabrique notre jeu de carte en mettant les hauteurs disponibles en argument:
from itertools import product def jeu(vals): """Ensemble des cartes selon les valeurs choisies (2 -> As ou 7 -> As) """ return product(vals,symboles)
On peut alors comparer les temps si l'on travaille avec ipython:
In [2]: %timeit ((valeur,couleur) for valeur in vals_32 for couleur in symboles) 302 ns ± 0.932 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) In [3]: %timeit jeu(vals_32) 264 ns ± 1.39 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
302 nanosecondes contre 264 nanosecondes: c'est bien équivalent d'après la documentation:
itertools.product(*iterables, repeat=1) Cartesian product of input iterables. Equivalent to nested for-loops in a generator expression. For example, product(A, B) returns the same as ((x,y) for x in A for y in B). The nested loops cycle like an odometer with the rightmost element advancing on every iteration. This pattern creates a lexicographic ordering so that if the input’s iterables are sorted, the product tuples are emitted in sorted order. To compute the product of an iterable with itself, specify the number of repetitions with the optional repeat keyword argument. For example, product(A, repeat=4) means the same as product(A, A, A, A). This function is equivalent to the following code, except that the actual implementation does not build up intermediate results in memory: def product(*args, repeat=1): # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111 pools = [tuple(pool) for pool in args] * repeat result = [[]] for pool in pools: result = [x+[y] for x in result for y in pool] for prod in result: yield tuple(prod)
La dernière remarque nous indique que la gestion de la mémoire est meilleure avec product.
En fait, sur Python, nous allons voir que la gestion de la mémoire (qui ne devrait pas parasiter nos idées mathématiques) produit d'étranges différences de performances aux yeux d'un(e) mathématicien(ne).
Il est normalement plus clair de travailler en créant des fonctions intermédiaires mais cela semble ralentir Python.
Cela va être marquant au moment de créer l'ensemble des mains de 5 cartes. On va utiliser la fonction combinations de itertools :
itertools.combinations(iterable, r) Return r length subsequences of elements from the input iterable. Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, the combination tuples will be produced in sorted order. Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will be no repeat values in each combination. The number of items returned is n! / r! / (n-r)! when 0 <= r <= n or zero when r > n.
C'est bien ce qu'il nous faut : le nombre de mains de 5 cartes dans un jeu de $n$ cartes est en effet $n \choose 5$. On peut alors proposer:
def mains(vals): """Ensemble des sous-ensembles de jeu de cardinal 5 : c'est donc l'ensemble des mains de 5 cartes""" return combinations(jeu(vals), 5)
ou
def mains(vals): return combinations(product(vals,symboles), 5)
ou
mains_32 = combinations(product(vals_32,symboles), 5)
Lançons la course:
In [14]: %timeit mains(vals_32) 100000 loops, best of 3: 2.29 us per loop In [15]: %timeit combinations(product(vals_32,symboles),5) 100000 loops, best of 3: 2.06 us per loop In [16]: %timeit mains_32 10000000 loops, best of 3: 25.7 ns per loop
La dernière solution est 100 fois plus rapide. Le problème, c'est que mains_32 est à usage unique : une fois que l'itérateur a été utilisé, il a en même temps été vidé, ce qui permet cette rapidité.
Mais bon, il faut rester simple et proche du problème mathématique donc nous utiliserons les fonctions "mains" sans rentrer dans les détails.
Dénombrer les mains
Il ne reste plus qu'à faire des tests sur nos ensembles de mains et compter les mains qui les passent.
Nous aurons besoin de dresser la liste des hauteurs d'une main et celle des couleurs d'une main.
Nous allons utiliser la très importante fonction map qui applique une fonction à tous les éléments d'un itérateur.
Par exemple, si je "map" la liste [1,2,3] par la fonction carrée, j'aurai [1,4,9].
On peut aussi faire des constructions par compréhension.
Ici :
def hauteurs(main): """Liste des hauteurs d'une main""" return map(hauteur,main) def couleurs(main): """Ensemble des couleurs d'une main""" return map(couleur,main)
Ensuite, il me faut compter les sorties identiques. Il existe un outil Python tout fait pour ça : la fonction Counter de la bibliothèque collections. Par exemple:
In [62]: from collections import Counter In [63]: Counter("maman papa") Out[63]: Counter({'a': 4, 'p': 2, 'm': 2, ' ': 1, 'n': 1})
On reçoit donc un dictionnaire des éléments de l'itérateur classés selon leurs fréquences.
Ici, les clés du dictionnaire sont les lettres et les valeurs associées sont les fréquences.
On utilisera aussi le test in qui répond vrai si l'élément testé est dans l'itérateur:
In [65]: 'a' in "maman" Out[65]: True In [66]: 'z' in "maman" Out[66]: False
Un carré au poker contient donc un 4 dans son ensemble de valeurs (obtenu avec la méthode values en Python).
def est_carre(main): """Teste si une main contient quatre cartes de même hauteur""" return 4 in Counter(hauteurs(main)).values()
Le résultat est un booléen : True ou False.
In [69]: m = (('Sept', 'Trefle'), ('Sept', 'Carreau'), ('Sept', 'Coeur'), ('Sept', 'Pique'), ('Huit', 'Trefle')) In [70]: est_carre(m) Out[70]: True
Ensuite, nous voudrions compter le nombre de carrés dans un jeu. Une fonction bien surchargée à la mode Python va être ici bien pratique : c'est la fonction sum.
Elle fait ce qu'on attend d'elle:
In [71]: sum([1,2,3]) Out[71]: 6
et même plus, pour ce qui est des booléen:
In [72]: sum([True,True,True,False,True]) Out[72]: 4
Elle nous permet donc de compter les mains qui ont passé le test:
def compte_mains(test,vals): """Compte combien de fois le prédicat est vrai dans l'itérable""" return sum(map(test, mains(vals)))
Cela nous permet de compter les carrés d'un jeu de 32 ou 52 cartes (mais pour 52, c'est un peu long...):
In [75]: compte_mains(est_carre,vals_32) Out[75]: 224 In [76]: %timeit compte_mains(est_carre,vals_32) 1 loops, best of 3: 1.7 s per loop In [77]: compte_mains(est_carre,vals_52) Out[77]: 624 In [78]: %timeit compte_mains(est_carre,vals_52) 1 loops, best of 3: 22.1 s per loop
On aurait pu procéder autrement. Par exemple, en s'occupant de l'ensemble des hauteurs qui sera donc constitué de 1 et 4:
def est_carre(main): return {1,4} == set(Counter(hauteurs(main)).values())
Ou encore, en ordonnant la liste des hauteurs (avec la fonction sorted qui trie une liste en Python) qui doit donc être [1,4]:
def est_carre(main): return [1,4] == sorted(list(Counter(hauteurs(main)).values()))
On trouve dans tous les cas 224 qui est ${8 \choose 1} \times {4 \choose 4} \times {{32-4} \choose 1}$: une hauteur parmi 8, quatre cartes dans cette hauteur et 1 carte parmi les 28 qui restent.
Pour la plupart des autres mains, on agit de manière similaire:
def est_full(main): """Teste si une main contient trois cartes de même hauteur et deux d'une autre""" return {2,3} == set(Counter(hauteurs(main)).values()) def est_double_paire(main): """Teste si une main contient 2 cartes de même hauteur et deux d'une autre""" return [1,2,2] == sorted(list(Counter(hauteurs(main)).values())) def est_brelan(main): """Teste si une main contient 3 cartes de même hauteur""" return [1,1,3] == sorted(list(Counter(hauteurs(main)).values())) def est_paire(main): """Teste si une main contient 2 cartes de même hauteur""" return [1,1,1,2] == sorted(list(Counter(hauteurs(main)).values()))
On obtient:
In [79]: compte_mains(est_full,vals_32) Out[79]: 1344 In [80]: compte_mains(est_brelan,vals_32) Out[80]: 10752 In [81]: compte_mains(est_double_paire,vals_32) Out[81]: 24192 In [82]: compte_mains(est_paire,vals_32) Out[82]: 107520
Il ne reste plus qu'à s'occuper des couleurs et des quintes, en faisant attention aux quintes flush : une couleur ne doit pas être une quinte en même temps et vice-versa.
Pour trouver les quintes, on peut utiliser islice qui, comme son nom l'indique, coupe un itérateur en tranches:
itertools.islice(iterable, start, stop[, step]) Make an iterator that returns selected elements from the iterable. If start is non-zero, then elements from the iterable are skipped until start is reached. Afterward, elements are returned consecutively unless step is set higher than one which results in items being skipped. If stop is None, then iteration continues until the iterator is exhausted, if at all; otherwise, it stops at the specified position. Unlike regular slicing, islice() does not support negative values for start, stop, or step. Can be used to extract related fields from data where the internal structure has been flattened (for example, a multi-line report may list a name field on every third line). Equivalent to: def islice(iterable, *args): # islice('ABCDEFG', 2) --> A B # islice('ABCDEFG', 2, 4) --> C D # islice('ABCDEFG', 2, None) --> C D E F G # islice('ABCDEFG', 0, None, 2) --> A C E G s = slice(*args) it = iter(range(s.start or 0, s.stop or sys.maxsize, s.step or 1)) nexti = next(it) for i, element in enumerate(iterable): if i == nexti: yield element nexti = next(it) If start is None, then iteration starts at zero. If step is None, then the step defaults to one.
Ce qui donne:
def meme_couleur(main): """Teste si une main contient cinq cartes de même couleur""" return len(Counter(couleurs(main)).keys()) == 1 def suites(vals): """Ensemble d'ensembles de hauteurs de mains contenant une quinte""" return [set(islice(vals,k,k+5,1)) for k in range(len(vals) - 4)] def est_quinte_32(main): """Teste si une main de 32 cartes contient une quinte avec des couleurs différentes""" return (set(hauteurs(main)) in suites(vals_32)) and not meme_couleur(main) def est_quinte_52(main): """Teste si une main de 52 cartes contient une quinte avec des couleurs différentes""" return (set(hauteurs(main)) in suites(vals_52)) and not meme_couleur(main) def est_couleur_32(main): """Teste si une main de 32 cartes contient une couleur qui n'est pas une quinte""" return not (set(hauteurs(main)) in suites(vals_32)) and meme_couleur(main) def est_couleur_52(main): """Teste si une main de 52 cartes contient une couleur qui n'est pas une quinte""" return not (set(hauteurs(main)) in suites(vals_52)) and meme_couleur(main) def est_flush_32(main): """Teste si une main de 32 cartes contient une couleur qui est une quinte""" return (set(hauteurs(main)) in suites(vals_32)) and meme_couleur(main) def est_flush_52(main): """Teste si une main de 52 cartes contient une couleur qui est une quinte""" return (set(hauteurs(main)) in suites(vals_52)) and meme_couleur(main)
On obtient:
In [84]: compte_mains(est_quinte_32,vals_32) Out[84]: 4080 In [85]: compte_mains(est_couleur_32,vals_32) Out[85]: 208 In [86]: compte_mains(est_flush_32,vals_32) Out[86]: 16
Il ne reste plus qu'à le vérifier en travaillant sur les coefficients binomiaux.
le code complet
from collections import Counter from itertools import product,combinations, islice # Liste des symboles des cartes symboles = ['Trefle','Carreau','Coeur','Pique'] # Liste des valeurs dans un jeu de 32 cartes vals_32 = ['Sept','Huit','Neuf','Dix','Valet','Dame','Roi','As'] # Ensemble des valeurs dans un jeu de 52 cartes vals_52 = ['Deux','Trois','Quatre','Cinq','Six'] + vals_32 def jeu(vals): """Ensemble des cartes selon les valeurs choisies 2 -> As ou 7 -> As""" return product(vals,symboles) def hauteur(carte): """Hauteur d'une carte. Une carte est un couple (valeur,symbole)""" return carte[0] def couleur(carte): """Couleur d'une carte. Une carte est un couple (valeur,symbole)""" return carte[1] def mains(vals): """Ensemble des sous-ensembles de jeu de cardinal 5 : c'est donc l'ensemble des mains de 5 cartes""" return combinations(jeu(vals), 5) def hauteurs(main): """Liste des hauteurs d'une main""" return map(hauteur,main) def couleurs(main): """Ensemble des couleurs d'une main""" return map(couleur,main) def est_carre(main): """Teste si une main contient quatre cartes de même hauteur""" return 4 in Counter(hauteurs(main)).values() def est_full(main): """Teste si une main contient trois cartes de même hauteur et deux d'une autre""" return {2,3} == set(Counter(hauteurs(main)).values()) def est_double_paire(main): """Teste si une main contient 2 cartes de même hauteur et deux d'une autre""" return [1,2,2] == sorted(list(Counter(hauteurs(main)).values())) def est_brelan(main): """Teste si une main contient 3 cartes de même hauteur""" return [1,1,3] == sorted(list(Counter(hauteurs(main)).values())) def est_paire(main): """Teste si une main contient 2 cartes de même hauteur""" return [1,1,1,2] == sorted(list(Counter(hauteurs(main)).values())) def meme_couleur(main): """Teste si une main contient cinq cartes de même couleur""" return len(Counter(couleurs(main)).keys()) == 1 def suites(vals): """Ensemble d'ensembles de hauteurs de mains contenant une quinte""" return [set(islice(vals,k,k+5,1)) for k in range(len(vals) - 4)] def est_quinte_32(main): """Teste si une main de 32 cartes contient une quinte avec des couleurs différentes""" return (set(hauteurs(main)) in suites(vals_32)) and not meme_couleur(main) def est_quinte_52(main): """Teste si une main de 52 cartes contient une quinte avec des couleurs différentes""" return (set(hauteurs(main)) in suites(vals_52)) and not meme_couleur(main) def est_couleur_32(main): """Teste si une main de 32 cartes contient une couleur qui n'est pas une quinte""" return not (set(hauteurs(main)) in suites(vals_32)) and meme_couleur(main) def est_couleur_52(main): """Teste si une main de 52 cartes contient une couleur qui n'est pas une quinte""" return not (set(hauteurs(main)) in suites(vals_52)) and meme_couleur(main) def est_flush_32(main): """Teste si une main de 32 cartes contient une couleur qui est une quinte""" return (set(hauteurs(main)) in suites(vals_32)) and meme_couleur(main) def est_flush_52(main): """Teste si une main de 52 cartes contient une couleur qui est une quinte""" return (set(hauteurs(main)) in suites(vals_52)) and meme_couleur(main) def compte_mains(test,vals): """Compte combien de fois le prédicat est vrai dans l'itérable""" return sum(map(test, mains(vals)))