Ci-dessous, les différences entre deux révisions de la page.
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:51] tyrtamos |
permutations [2010/01/09 11:27] tyrtamos |
||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
====== Permutations ====== | ====== Permutations ====== | ||
- | **//En construction// | + | ===== Objectif ===== |
- | Référence pour la définition: voir [[http:// | + | Exemple: soit une liste d' |
- | Par exemple, | + | * on veut savoir |
- | ==== 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: | ||
+ | |||
+ | ===== Calcul du nombre de permutations ===== | ||
+ | |||
+ | ==== Nombre de permutations sans répétition | ||
Dans l' | Dans l' | ||
Ligne 19: | Ligne 26: | ||
""" | """ | ||
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: | ||
</ | </ | ||
- | === 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à, on a un objet plus complexe, composés d' | ||
Ligne 119: | Ligne 126: | ||
* dans le cas contraire, il suffit d' | * dans le cas contraire, il suffit d' | ||
- | ==== 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, | On sait maintenant calculer le **nombre** de permutations, | ||
Ligne 144: | Ligne 151: | ||
\\ | \\ | ||
- | Bon. Dans vos essais, soyez raisonnables: | + | Bon. Dans vos essais, soyez raisonnables: |
- | === 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, | + | Au lancement de la fonction permutliste([1, |
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, | Même principe que précédemment, | ||
Ligne 275: | Ligne 282: | ||
+ | \\ | ||
+ | Amusez-vous bien! | ||