Outils pour utilisateurs

Outils du site


permutations

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Dernière révision Les deux révisions suivantes
permutations [2010/01/09 08:57]
tyrtamos
permutations [2010/01/09 11:10]
tyrtamos
Ligne 3: Ligne 3:
 **//En construction//​** **//En construction//​**
  
-Référence pour la définition:​ voir [[http://​fr.wikipedia.org/​wiki/​Permutation]]+===== Objectif =====
  
-Par exemple, les permutations de trois objets ​distincts AB et C sontABC, ACB, BAC, BCA, CAB, CBA. +Exemple: soit une liste d'objets ​[1,2,3]:
  
-==== Calcul du nombre ​de permutations ====+  * on veut savoir les présenter ​de toutes les façons possibles: %%[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]%%,
  
-=== Nombre de permutations sans répétition ===+  * en tenant compte si nécessaire des répétitions (ex: [1,2,2] 
 + 
 +  * et on veut savoir combien il y en a. 
 + 
 +\\ 
 +Référence externe pour la définition:​ voir [[http://​fr.wikipedia.org/​wiki/​Permutation]] 
 + 
 +===== Calcul du nombre de permutations ===== 
 + 
 +==== Nombre de permutations sans répétition ​====
  
 Dans l'​exemple ci-dessus, il y a 6 permutations de ces 3 objets, et ce nombre de permutations se calcule simplement: il est égal à factorielle 3 = 6. Dans l'​exemple ci-dessus, il y a 6 permutations de ces 3 objets, et ce nombre de permutations se calcule simplement: il est égal à factorielle 3 = 6.
Ligne 19: Ligne 28:
     """​Calcule le nombre de permutations de n objets (n: entier >= 0)"""​     """​Calcule le nombre de permutations de n objets (n: entier >= 0)"""​
     x = 1     x = 1
-    for i in xrange(2, n[0]+1):+    for i in xrange(2, n+1):
         x *= i         x *= i
     return x     return x
Ligne 31: Ligne 40:
 </​code>​ </​code>​
  
-=== Nombre de permutations avec répétition ===+==== Nombre de permutations avec répétition ​====
  
 Là, on a un objet plus complexe, composés d'​éléments dont certains peuvent se répéter. ​ Là, on a un objet plus complexe, composés d'​éléments dont certains peuvent se répéter. ​
Ligne 119: Ligne 128:
   * dans le cas contraire, il suffit d'​ajouter la liste des répétitions.   * dans le cas contraire, il suffit d'​ajouter la liste des répétitions.
  
-==== Liste des permutations de chaînes de caractères présentées dans une liste ====+===== Liste des permutations de chaînes de caractères présentées dans une liste =====
  
 On sait maintenant calculer le **nombre** de permutations,​ mais on voudrait maintenant connaitre la **liste** des permutations elle-même. On sait maintenant calculer le **nombre** de permutations,​ mais on voudrait maintenant connaitre la **liste** des permutations elle-même.
Ligne 146: Ligne 155:
 Bon. Dans vos essais, soyez raisonnables:​ n'​oubliez pas que le nombre de permutation augmente très rapidement avec la longueur de la liste seq (factorielle de len(seq)). Ainsi, une liste toute simple comme seq = [1,​2,​3,​4,​5,​6,​7,​8,​9] donnera (en moins d'une seconde avec le code non-récursif) la liste des 362880 façons de présenter la liste seq... Bon. Dans vos essais, soyez raisonnables:​ n'​oubliez pas que le nombre de permutation augmente très rapidement avec la longueur de la liste seq (factorielle de len(seq)). Ainsi, une liste toute simple comme seq = [1,​2,​3,​4,​5,​6,​7,​8,​9] donnera (en moins d'une seconde avec le code non-récursif) la liste des 362880 façons de présenter la liste seq...
  
-=== Code non récursif ===+==== Code non récursif ​====
  
 Le code non-récursif est ici assez concis et très rapide (2 à 3 fois plus que le code récursif). Le code non-récursif est ici assez concis et très rapide (2 à 3 fois plus que le code récursif).
Ligne 190: Ligne 199:
  
  
-=== Code récursif ===+==== Code récursif ​====
  
 Voilà le code récursif: Voilà le code récursif:
Ligne 223: Ligne 232:
  
  
-==== Liste des permutations des caractères d'une chaîne de caractères ====+===== Liste des permutations des caractères d'une chaîne de caractères ​=====
  
 Même principe que précédemment,​ à part qu'on cherche les permutations des caractères dans une chaîne. Par exemple, '​ABC'​ => ['​ABC',​ '​ACB',​ '​BAC',​ '​BCA',​ '​CAB',​ '​CBA'​] Même principe que précédemment,​ à part qu'on cherche les permutations des caractères dans une chaîne. Par exemple, '​ABC'​ => ['​ABC',​ '​ACB',​ '​BAC',​ '​BCA',​ '​CAB',​ '​CBA'​]
permutations.txt · Dernière modification: 2010/01/09 11:27 par tyrtamos