Archives par étiquette : permutation

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

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

losange-anagrammes
(Vérification avec le programme Python évoqué ici)

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

anagrammes-messages

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

anagrammes-chercherez

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 :

anagrammes-py

Les anagrammes mathématiques d’ananas …

Pineapple Fruit
Creative Commons License photo credit: Alex E. Proimos

Combien ananas a-il d’anagrammes ? Si toutes les lettres étaient différentes on répondrait sans hésiter factorielle de 6 (6!=720) mais les 3 A et les deux N nous obligent à réfléchir davantage…

Pour le doublons N (Nous avons étudier ce cas précédemment) il suffira de diviser par 2… Mais pour les 3A ?
L’erreur commune (et attendue) est la division par 3 (donc par 3 fois 2, soit par 6 pour trouver en fin de compte 120=5!)

Réfléchissons mieux ;)

Nos 3 A que l’on pourrait baptiser A1, A2 et A3 ont combien de façons de s’agencer les uns par rapports aux autres ?A1 A2 A3
A1 A3 A2
A2…

Nous avons déjà étudié ce problème c’est le nombre de permutation d’un ensemble à 3 éléments !
Il ya 3!=6 façons de permuter nos 3 AEt tout se tient ! Il y avait effectivement 2!=2 façons de permuter nos N

La réponse au problème est maintenant limpide :

factorielles

Il y a 60 anagrammes à ANANAS

Il peut arriver de douter de son raisonnement et le développement d’un petit programme en Python peut nous conforter :

1 : a a a s n n
2 : a a a n s n
3 : a a a n n s
4 : a a s a n n
5 : a a s n a n
6 : a a s n n a
7 : a a n a s n
8 : a a n a n s
9 : a a n s a n
10 : a a n s n a
11 : a a n n a s
12 : a a n n s a
13 : a s a a n n
14 : a s a n a n
15 : a s a n n a
16 : a s n a a n
17 : a s n a n a
18 : a s n n a a
19 : a n a a s n
20 : a n a a n s
21 : a n a s a n
22 : a n a s n a
23 : a n a n a s
24 : a n a n s a
25 : a n s a a n
26 : a n s a n a
27 : a n s n a a
28 : a n n a a s
29 : a n n a s a
30 : a n n s a a
31 : s a a a n n
32 : s a a n a n
33 : s a a n n a
34 : s a n a a n
35 : s a n a n a
36 : s a n n a a
37 : s n a a a n
38 : s n a a n a
39 : s n a n a a
40 : s n n a a a
41 : n a a a s n
42 : n a a a n s
43 : n a a s a n
44 : n a a s n a
45 : n a a n a s
46 : n a a n s a
47 : n a s a a n
48 : n a s a n a
49 : n a s n a a
50 : n a n a a s
51 : n a n a s a
52 : n a n s a a
53 : n s a a a n
54 : n s a a n a
55 : n s a n a a
56 : n s n a a a
57 : n n a a a s
58 : n n a a s a
59 : n n a s a a
60 : n n s a a a

Pour les accrocs au développement, je leur offre en prime le code de ce petit programme en Python :

# -*- coding: utf-8 -*-

# création du dictionnaire, et variables globales #
lettre={}
compteur=1

def affiche (x,n=0):
    global chaine, compteur

    if len(x)==1 and x.values()[0]==1:
        chaine[n]= x.keys()[0]
        print str(" "*(20-len(str(compteur))))+ str(compteur) + "  : ",
        for l in chaine:
            print l,
        print
        compteur=compteur+1

    else :
          for lettre in x.keys():
            y = x.copy()
            chaine[n]=lettre
            if x[lettre]>1 :
               y[lettre]=y[lettre]-1
            else :
                del(y[lettre])
            affiche(y,n+1)

mot=raw_input("Entrez votre mot : ")

a=0
while(a      if lettre.has_key(mot[a]):
         lettre[mot[a]]=lettre[mot[a]]+1
      else:
         lettre[mot[a]]=1
      a=a+1
print "liste des anagrammes"
chaine=['']*len(mot)
affiche(lettre)

a=raw_input()

Ne cliquez que si vous avez compris ;) (Scoopeo)

RASOIR est une anagramme de ROSIRA, mais combien RASOIR a-t-il d’anagrammes ?

ROSIRA

Le problème est moins simple que les précédents et la réponse (évidente) 6!=720 est erronée à cause du double R.

R1ASOIR2 est le même mot que R2ASOIR1

On a donc compté deux fois trop de mots!

La réponse est donc 6!/2=360 anagrammes pour le mot RASOIR…

Plus dur: ANANAS ne me semble pas avoir d’anagrammes au sens littéraire, mais combien en a-t-il au sens mathématique ?

Mathématiques pour les nuls : Dénombrement et factorielles (4)

 

Nous avons découvert dans de précédents billets que le nombre de permutations d’un ensemble à n éléments est n! (factorielle n):

n!=1x2x3x…(n-1)xn

Parlons d’anagrammes :

 

anagrammes

Il est des anagrammes amusantes :
CHIEN est une anagramme de NICHE
POLICE est une anagramme de PICOLE

Si on compte également les mots qui ne veulent rien dire, combien CHIEN et POLICE ont-ils d’anagrammes ?

Pour CHIEN :
On peut permuter les 5 lettres de 5! façons différente, il y a donc 5!=120 anagrammes différentes.

Pour POLICE : 6!=720 anagrammes.

Tout ceci est très simple. Trop simple ?

RASOIR est une anagramme de ROSIRA, mais combien RASOIR a-t-il d’anagrammes ?
Voyez-vous pourquoi le problème est différent ?