Vous ne croirez pas le nombres de mots possibles dans une main de Scrabble!!

Le Scrabble, un jeu fortement lié au mathématique.

Le scrabble, un jeu de société apparu en 1948 dont le but est de concevoir un mot du dictionnaire avec une suite de lettres donnée. Plus le mot et long et les lettres utilisés sont non communs (tel que le z) et plus le mot rapporte de points. Ici nous nous intéressons pas au nombres de points mais au nombres de permutations que peut contenir une main de scrabble.

Si je vous donne comme lettres A-B-C, combien de combinaison possible pouvez faire sur 3 lettres? 2? 1? Réponse: 6-6-3 pour un total de 15 mots possibles, facile non? On peut le vérifier avec un graphe comme ci-dessous.

Alors si je vous donne les lettres D-I-F-F-I-C-I-L-E? Essayé de le faire mentalement ou d'utiliser un graphe risque de prendre beaucoup trop de temps, et c'est dans ce blog que nous allons trouver une formule et un programme nous permettant de rendre cette tache plus facile.

Tout d'abord nous devons expliquer concrètement ce que nous cherchons.

  • "Pour une liste de lettres données, trouver le nombres de mots que peut formé cette liste."

Et ensuite depuis cette liste de mots, de trouvée tous les mots valables dans un jeu de scrabble.

Et le but de ce billet de blog est ainsi de :

  • Depuis une liste de lettres données, donner une borne supérieure à la taille de scrabble(s) (avec s: la liste de lettres données), en fonction de la longueur de s (indépendemment du dictionnaire), trouvée ensuite tous les mots valables que ces lettres peuvent formées valables dans un dictionnaire (ici pour ce blog, une liste de mots données via un fichier.txt).

Commençons donc avec l'exemple D-I-F-F-I-C-I-L-E. Alors pour 9 lettres il suffit d'utilisé la formule vu en cours.

  • Soit total = la longueur de la liste de lettres données
  • x = le nombre de lettres distinct
  • a',b', ..., z'= le nombre de lettres répéter correspondante

    \[    \frac{total!}{(total-x)!}   \binom{total - x}{a'}  \binom{total-x-a'}{b'}  ...  \binom{total-x-a'...-y'}{z'}   \]

Cette fonction nous donne le résultat avec notre exemple:

  • total = 9 avec D,I,F,F,I,C,I,L,E
  • x = 4 avec D,C,L,E
  • f' = 2 avec F,F
  • i'= 3 avec I,I,I

    \[ \frac{9!}{(9-4)!} \binom{9-4}{2} \binom{9-4-2}{3}= 3024 *10 * 1 = 30240 \]

Il y a donc 30240 mots différents pour 9 lettres de longueur 9.

Mais on peut aussi voir le calcul de cette façon qui peut rendre cela plus simple:

  • Les 9 lettres de DIFFICILE ont 9!=362880 permutation
  • f' = 2, il y a 2! permutations
  • i' = 3, il y a 3! permutations

    \[\frac{9!}{(3!*2!)} = 30240 \]

Mais c'est 2 fonctions ne permettent que de calculer le nombres de mots de taille n pour n cases. En effet lorsque la taille des cases diminue ces fonctions ne marche pas.

On peut alors essayer de trouver une autre façon de calculer. Au lieu d'essayer de calculer directement le nombre de mots, on peut calculer le nombre de doublon d, puis de le soustraire au nombre de mots avec doublon.

Pour calculer d pour f', on determine d'abord le nombre de fois où les lettres répétés apparaissent. Avec m = longeur du mot qu'on essaye de former, on fait :

    \[c = \frac{total!}{(total-m)!}\]

si il n'existe pas de mot sans f

    \[c = \frac{total!}{(total-m)!} - \frac{(x + i')!}{(f')!}\]

si il existe des mots sans f

Maintenant qu'on a c, on divise c par le nombre de façon de placer les f (ici 2), et de multiplier par le même chiffre - 1 (1). On obtient enfin d.

On soustrait le nombre de mot possible avec doublon par d, puis on refait le même processus pour determiner le d pour i' en remplaçant la premiere division de c par le resultat.

Il n'existe malheureusement pas de formule simple permettant de calculer facilement le nombre de mots (sans doublon), mais on peut le trouver en calculant le nombre de doublon pour chaque lettre puis de soustraire ce resultat.

Auteurs : Lucie Danis, Anthony Phothirath et Julien Richard.

0 Cliquer pour recommander cet article