Warning: Undefined array key "DOKU_PREFS" in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/common.php on line 2082
permutations [Les recettes Python de Tyrtamos]

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Piste:
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 A, B et C sont: ABC, 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 de tyrtamos

Outils de la page

Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : CC Attribution-Noncommercial-Share Alike 4.0 International
CC Attribution-Noncommercial-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki