Scrabble

Introduction

Le Scrabble a été créé en 1931 par Alfred Mosher Butts. Le but du jeu est de poser une ou plusieurs lettres à tour de rôle sur un plateau afin de former des mots. Chaque joueur pioche 7 lettres en début de partie et le premier mot doit recouvrir la case du milieux et faire au moins deux lettres.

Nous souhaitons donc réaliser la génération des mots possibles de la main d'un joueur. Pour cela, nous allons définir un algorithme qui renvoie la liste des combinaisons de lettre possible présente dans le dictionnaire.  

En effet, le principe du code demandé et de calculer la liste d’anagramme possible de chaque combinaisons de caractère d’une chaine de caractère.

Nous allons donc commencé par :

  • Définir ce qu'est un anagramme.
  • Puis, expliquer le calculs du nombre possible d'anagramme en générale.
  • Donner le nombre de combinaisons de lettres possible dans notre cas.
  • Nous présenterons ensuite un algorithme donnant la liste de toutes ces combinaisons.

Qu'est qu'un anagramme ?

Du grec anagramma, renversement de lettres, une anagramme est un mot ou un ensemble de mots construit en changeant les lettres d'un autre mot, les disposant dans un ordre différent. 

Par exemple, navire est une anagramme de ravine, proies de poires.

Une anagramme peut être un mot significatif (présent dans le dictionnaire) ou non. Mais dans notre cas, il est demandé que le programme retourne des mots existants.

C’est facile de créer une anagramme, il suffit de changer la position d’une ou plusieurs lettres du même mot. C’est ce qu’on a fait dans navire pour obtenir ravine.

Exemples d'anagrammes

  • Races, Sacre ;
  • Gardée, Gradée ;
  • Poires, Proies ;
  • Pléonasme, Néoplasme.

Calculs mathématiques d’anagrammes

On peut mathématiquement calculer le nombre d’anagrammes en procédant à l'analyse combinatoire qui consiste en une permutation des lettres d'un mot.

Pour connaître le nombre d'anagrammes qu’il est possible de former à partir d’un mot (sans lettres répétées), il suffit de faire une permutation avec le nombre de lettres qu’il contient. Dans la maison du mot "maison" contenant six lettres, le résultat est 6! (6 x 5 x 4 x 3 x 2 x 1) = 720. Il est donc possible de construire 720 anagrammes existants ou non avec le mot « maison ».

Dans notre cas il n’est pas seulement demandé de donné les anagrammes contenant exactement le même nombre de lettre que le mot de départ, mais la totalité des anagrammes possibles de 1 à 6 lettres.

Donc pour former ces anagrammes il suffit de former des mots  de 5 lettres parmi les 6 lettres du mot d’origine, puis de 4 et ainsi de suite.

Il s’agit d’une suite ordonné et sans répétition, ce qui donne donc le calcul suivant :

Code :

scrabble(s, ancien=""):
  liste_deja_parcouru := [];
  liste_totale :=[];
  Pour chaque c de s:
    Si liste_deja_parcouru ne contient pas c :
      Si ancien+c est dans le dictionnaire alors:
         liste_totale += [ancien+c];
      liste_totale += scrabble(s sans c, ancien+c);
      liste_deja_parcouru += [c];
  Fin Pour chaque
  retourne liste_totale;
Fin

Fonctionnement :

Le principe de l'algorithme est simple. Dans un premier temps, l'utilisateur doit entrer une suite de lettre (exemple: la liste de lettre présente dans sa main.) de maximum 7 lettres, car sinon, le temps de calcul est trop important.

De là, l'algorithme décrit ci-dessus va commencer par initialiser une liste vide dans laquelle il va ajouter les mots possibles, en vérifiant qu'ils soit présent dans le fichier 'liste_francais.txt'.

Pour ce faire, pour chaque lettre, l'algorithme va ajouter a la case suivante le mot de la case précédente ajouté à la lettre courante.

Pour la pratique :

/* Cliquez pour recommencer ! */

4 Cliquer pour recommander cet article