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

Warning: Undefined array key -1 in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/html.php on line 1458

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
Prochaine révision 		Révision précédente
permutations [2010/01/09 08:57]
tyrtamos 		permutations [2010/01/09 11:27] (Version actuelle)
tyrtamos
Ligne 1: Ligne 1:
 ====== Permutations ====== ====== Permutations ======
  
-**//En construction//**+===== Objectif =====
  
-Référence pour la définition: voir [[http://fr.wikipedia.org/wiki/Permutation]]+Exemple: soit une liste d'objets [1,2,3]:
  
-Par exemple, les permutations de trois objets distincts A, B et C sont: ABC, ACB, BAC, BCA, CAB, CBA. +  * 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]]%%,
  
-==== Calcul du nombre de permutations ====+  * en tenant compte si nécessaire des répétitions (ex: [1,2,2]
  
-=== Nombre de permutations sans répétition ===+  * 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 26:
     """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 38:
 </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 126:
   * 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 144: Ligne 151:
  
 \\ \\
-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. Cette liste sera tellement longue qu'elle risque même de ne pas pouvoir s'afficher sur votre PC...
  
-=== 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 197:
  
  
-=== Code récursif ===+==== Code récursif ====
  
 Voilà le code récursif: Voilà le code récursif:
Ligne 214: Ligne 221:
 On ne donne jamais le 3ème argument k qui n'est utilisé que comme variable interne. On ne donne jamais le 3ème argument k qui n'est utilisé que comme variable interne.
  
-Au lancement de la fonction, permutliste([1,2,3,4]), le 1er passage (sans la récursion), donnera avec k=0 les 4 rotations: [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]. Pour chacune de ces valeurs, un appel récursif avec l'indice de rotation k+1 permettra de retourner toutes les séquences de rotation suivantes. Etc... jusqu'à ce que k=len(seq)-1 auquel cas il n'y a plus de rotation à faire.+Au lancement de la fonction permutliste([1,2,3,4]), le 1er passage (sans la récursion), donnera avec k=0 les 4 rotations: [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]. Pour chacune de ces valeurs, un appel récursif avec l'indice de rotation k+1 permettra de retourner toutes les séquences de rotation suivantes. Etc... jusqu'à ce que k=len(seq)-1 auquel cas il n'y a plus de rotation à faire.
  
 Ce code donne bien entendu les mêmes résultats que le code non-récursif. Ce code donne bien entendu les mêmes résultats que le code non-récursif.
Ligne 223: Ligne 230:
  
  
-==== 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.1263023824.txt.gz · Dernière modification: 2010/01/09 08:57 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