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
Prochaine révision
Révision précédente
permutations [2010/01/09 08:57]
tyrtamos
permutations [2010/01/09 11:27]
tyrtamos
Ligne 1: Ligne 1:
 ====== Permutations ====== ====== Permutations ======
  
-**//En construction//​**+===== Objectif =====
  
-Référence pour la définitionvoir [[http://​fr.wikipedia.org/​wiki/​Permutation]]+Exemplesoit une liste d'​objets ​[1,2,3]:
  
-Par exemple, ​les permutations ​de trois objets distincts A, B et C sontABCACBBACBCACABCBA. +  * 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, 12][321]]%%,
  
-==== 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 fonctionpermutliste([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.txt · Dernière modification: 2010/01/09 11:27 par tyrtamos