Le bilan sur les factorielles, permutations sans ou avec répétitions

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 )

from itertools import permutations

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

mot=input("Entrez un mot, Entrée pour terminer:     ")
num_str=str(len(mot))+"!"
num=fact(len(mot))
den_str=""
den=1


while mot!="":
    lettres=set(mot)

    for lettre in lettres:
        if mot.count(lettre)>1:
            den_str+=str(mot.count(lettre))+"! x "
            den*= fact(mot.count(lettre))
    if den==1:
        print(num_str +" = "+str(num))
    else:
        print(num_str+" / "+den_str[:-2]+" = "+str(num)+" / "+str(den) +" = " +str(int(num/den)))
    print(f"""{mot} a {str(int(num/den))} anagrammes""")

    deja_vues = set()
    numero = 0

    for permutation in permutations(mot):

        anagramme = "".join(permutation)

        if anagramme not in deja_vues:
            deja_vues.add(anagramme)

            numero += 1

            print(numero, anagramme, end="  ")

            if numero % 10 == 0:
                print()
    print()
    mot = input("Entrez un mot, Entrée pour terminer:     ")
    num_str = str(len(mot)) + "!"
    num = fact(len(mot))
    den_str = ""
    den = 1

Ce qui donne :

Remarque

Vous avez peut-être remarqué que dans le code j’utilise cette fois itertools.combinations ?