En mathématiques, la notion de permutation correspond simplement à un changement d’ordre des objets d’un ensemble (ordonné).
Si on considère par exemple les anagrammes du mot LOSANGE, on se pose la question de savoir combien de mots (pas au sens littéraire, ces suites de lettres n’ont pas besoin d’avoir un sens) on peut écrire avec les lettres :
L-O-S-A-N-G-E .
Les lettres étant toutes différentes, on parle de permutation sans répétition, et le nombre de ces permutations est la factorielle du nombre d’objet (ici, ce sont des lettres).
soit : 7!= 5040
Par contre dans le mot MESSAGES, la lettre E apparaît deux fois, tandis que le S apparaît 3 fois. On parle alors de permutation avec répétition.
Pour les dénombrer, on divise la factorielle du nombres d’objet (8!) par le produit des factorielles de deux et de trois (le nombre d’apparition des objets « répétés »):
On trouve : 8!/(2!x3!) = 40320 / 12 = 3360
On peut résumer la méthode à employer pour dénombrer les permutations avec répétitions :
– On compte le nombre d’objet (lettres).
CHERCHEREZ est écrit avec 10 lettres.
– On se construit un petit tableau avec les objets répétés:
- Objets : nombre de répétitions
- C : 2
- H : 2
- E : 3
- R : 2
Le nombre de permutation de CHERCHEREZ est 10! / (2! x 2! x 3! x 2!) = 10! / 48 =75600
Cette méthode algorithmique nous incite à développer un petit programme qui affichera le nombre d’anagrammes d’un mot entré au clavier par l’utilisateur. (Non plus en les listant comme dans l’exemple étudié la dernière fois mais en calculant )
def fact(n):
"renvoie la factorielle de n"
if n==1: return 1
else : return n*fact(n-1)
mot=raw_input("Entrez votre mot (ENTREE pour quitter) : ")
while mot<>"":
lettre={}
a=0
while(a1:
denominateur=denominateur*fact(a)
chaine=chaine + str(a) +"!"if chaine<>"" : chaine = "/(" + chaine + ")"
print len(mot),"!",chaine,"=",fact(len(mot)),"/",denominateur,
print "=",fact(len(mot))/denominateur
print "Le nombre d'anagrammes de ",mot," est : ",fact(len(mot))/denominateur
print
print
mot=raw_input("un autre mot ? (ENTREE pour quitter) : ")
Ce qui donne :
