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

--- permutations [2010/01/09 08:47]
tyrtamos
+++ permutations [2010/01/09 11:27]
tyrtamos
@@ Ligne 1: / Ligne 1: @@
 ====== Permutations ======
+===== Objectif =====
+Exemple: soit une liste d'objets [1,2,3]:
+  * 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]]%%,
+  * 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.
+On va donc reprendre le code de la factorielle dans sa version non récursive:
+<code python>
+def permut(n):
+    """Calcule le nombre de permutations de n objets (n: entier >= 0)"""
+    x = 1
+    for i in xrange(2, n+1):
+        x *= i
+    return x
+</code>
+Exemple d'utilisation:
+<code python>
+print permut(3)
+</code>
+==== 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.
+Par exemple: [1,2,2,3,4,5,5,5]. Il y a 8 objets, mais le 2 est mis 2 fois et le 5 est mis 3 fois.
+Ainsi, il y aura permut(8)=40320 façons de présenter cette liste, mais certaines seront identiques!
+On veut donc calculer ici le nombre de permutations //en ne comptant qu'une seule fois les permutations identiques//.
+Il suffit de diviser le nombre total de permutations par chacune des factorielles des répétitions.
+Pour reprendre l'exemple: %%permut(8)//(fact(2)*fact(3)) = 3360%%
+Voilà le code qui fait ça. Pour le lancer, on met comme paramètre le nombre d'objet à permuter, suivi éventuellement de la liste des répétitions:
+<code python>
+def permut(n, r=[]):
+    """Calcule le nombre de permutations avec ou sans répétition de n objets
+       r est la liste des éventuelles répétitions rencontrées dans les n objets
+       exemple: [1,2,2,3,4,5,5,5] => permut(8,[2,3])
+    """
+    x = 1
+    for i in xrange(2, n+1):
+        x *= i
+    for m in r:
+        y = 1
+        for i in xrange(2, m+1):
+            y *= i
+        x //= y
+    return x
+</code>
+Exemple:
+<code python>
+# objet de 8 éléments avec le 2 mis 2 fois et le 5 mis 3 fois
+seq = [1,2,2,3,4,5,5,5]
+# nombre total de permutation sans répétition
+print permut(len(seq))
+# nombre de permutations avec répétitions
+# (= en ne comptant qu'une seule fois les permutations identiques)
+print permut(len(seq), [2, 3])
+</code>
+Bien entendu, on peut calculer automatiquement la liste des répétitions des objets dans la liste des objets.
+Par exemple comme suit (code très auto-commenté!):
+<code python>
+def repetelem(seq):
+    """Donne la liste des répétitions > 1 des éléments dans la séquence seq"""
+    r = [] # pour enregistrer les éléments déjà traités
+    d = [] # pour enregistrer le nombre de répétitions > 1 des éléments
+    for elem in seq:
+        if (elem not in r): # si l'élément n'a pas encore été rencontré
+            r.append(elem)  # on l'enregistre
+            x = seq.count(elem)  # on compte le nb de fois qu'il existe dans seq
+            if x>1:  # s'il existe en plusieurs exemplaires
+                d.append(x)  # on enregistre le nombre de ses répétitions
+    return d  # on renvoie la liste des répétitions > 1 rencontrées
+</code>
+Exemple d'utilisation:
+<code python>
+seq = [1,2,2,3,4,4,4,5,6,6,6,6,6,6]
+print repetelem(seq)
+[2, 3, 6]
+print permut(len(seq))
+87178291200
+print permut(len(seq), repetelem(seq))
+10090080
+</code>
+S'il n'y a qu'une seule de ces 2 fonctions permut() à retenir (sans ou avec répétition), c'est bien celle avec répétition, parce qu'elle fait tout:
+  * s'il n'y a qu'un seul argument, c'est qu'on n'a pas de répétition (ou qu'on n'en tient pas compte).
+  * 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 =====
+On sait maintenant calculer le **nombre** de permutations, mais on voudrait maintenant connaitre la **liste** des permutations elle-même.
+Par exemple: trouver toutes les permutations possibles de [1, 2, 3], c'est à dire: [1, 2, 3], [1, 3, 2], [2, 3, 1], [2, 1, 3], [3, 1, 2], [3, 2, 1]
+Ça pourrait, bien sûr, être une liste de n'importe quoi: ['truc','machin','bidule'].
+Sont présentés ci-dessous un code non-récursif (que je conseille) et un code récursif. Ils sont basés sur le même principe: des rotations des éléments qui se trouvent entre l'indice k et la fin de liste.
+Par exemple pour seq=[1,2,3,4]:
+  * pour k=0, on aura les rotations: [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]
+  * pour k=1, on aura les rotations: [1,2,3,4], [1,3,4,2], [1,4,2,3]
+  * pour k=2, on aura les rotations: [1,2,3,4], [1,2,4,3]
+  * pour k=3, c'est à dire pour k=len(seq)-1, on n'a plus d'autre rotation que [1,2,3,4]
+Pour chaque k, il y a len(seq)-k rotations en tout (c'est à dire len(seq)-k-1 en plus du seq initial)
+Pour faire une rotation à partir de l'indice k, vous voyez comment on fait: z.append(z.pop(k)) retire l'élément d'indice k et le remet à la fin de la liste.
+\\
+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 ====
+Le code non-récursif est ici assez concis et très rapide (2 à 3 fois plus que le code récursif).
+Voilà le code:
+<code python>
+def permutliste(seq, er=False):
+    """Retourne la liste de toutes les permutations de la liste seq (non récursif).
+       si er=True: élimination des répétitions quand seq en a (ex: [1,2,2]
+    """
+    p = [seq]
+    n = len(seq)
+    for k in xrange(0,n-1):
+        for i in xrange(0, len(p)):
+            z = p[i][:]
+            for c in xrange(0,n-k-1):
+                z.append(z.pop(k))
+                if er==False or (z not in p):
+                    p.append(z[:])
+    return p
+</code>
+On peut améliorer sa présentation avec un tri (avec p.sort() ou sorted(p) par ex.).
+On a tenu compte d'un 2ème argument ici pour éviter les répétitions. En effet, quand la liste initiale seq contient des éléments qui se répètent, le résultat contiendra plusieurs listes identiques. Pour que ces listes identiques ne soient comptées qu'une seule fois, il suffit d'ajouter True comme 2ème argument au lancement de la fonction.
+Exemple d'utilisation:
+<code python>
+seq = [1,2,3]
+print permutliste(seq)
+[[1, 2, 3], [1, 3, 2], [2, 3, 1], [2, 1, 3], [3, 1, 2], [3, 2, 1]]
+seq = [1,2,2]
+print permutliste(seq)
+[[1, 2, 2], [2, 2, 1], [2, 1, 2], [1, 2, 2], [2, 1, 2], [2, 2, 1]]
+seq = [1,2,2]
+print permutliste(seq, True)
+[[1, 2, 2], [2, 2, 1], [2, 1, 2]]
+</code>
+==== Code récursif ====
+Voilà le code récursif:
+<code python>
+def permutliste(seq, er=False, k=0):
+    """retourne la liste de toutes les permutations de la liste seq (récursif)
+       si er=True: élimination des répétitions quand seq en a (ex: [1,2,2]
+    """
+    n = len(seq)
+    if k == n-1:
+        return []
+    p = []
+    z = seq[:]
+    for c in xrange(0, n-k):
+        if er==False or (z not in p):
+            p.append(z[:])
+            p.extend(permutliste(z, er, k+1)[1:])
+        z.append(z.pop(k))
+    return p
+</code>
+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.
+Ce code donne bien entendu les mêmes résultats que le code non-récursif.
+Si vous voulez un résultat plus "présentable", vous pouvez trier la liste résultat (ex: %%r.sort()%% ou %%sorted(r)%%).
+Et pour éviter les répétitions au cas où des éléments se répètent dans la liste seq, on ajoute simplement l'argument True comme pour le code non-récursif.
+===== 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']
+Utilisation possible (entre autres): recherche d'anagrammes (voir [[http://fr.wikipedia.org/wiki/Anagramme]])
+La solution de codage utilise l'une des fonctions précédentes qui traite les listes (Python est vraiment doué pour manipuler des listes!):
+<code python>
+def permutchaine(ch, er=False):
+    """retourne la liste de toutes les permutations des caractères de la chaine ch
+       avec er=True pour éviter les répétitions quand ch en a (ex: 'abb')
+    """
+    return [''.join(z) for z in permutliste(list(ch), er)]
+</code>
+<code python>
+# exemples d'utilisation:
+print permutchaine("ABC")  # affiche ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
+</code>
+Si vous voulez que la chaîne résultat soit rangée selon l'ordre alphabétique, ou même dans l'ordre alphabétique inverse:
+<code python>
+R=permutchaine("CBA")
+print R  # affiche: ['BCA', 'BAC', 'ABC', 'ACB', 'CAB', 'CBA']
+R.sort()
+print R  # affiche: ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
+R.reverse()
+print R  # affiche: ['CBA', 'CAB', 'BCA', 'BAC', 'ACB', 'ABC']
+</code>
+Il y a une utilisation très intéressante de permutchaine(): calculer toutes les permutations sans répétition d'une chaîne de bits:
+Par exemple:
+<code python>
+print sorted(permutchaine('1100', True),reverse=True)
+</code>
+Ce qui affichera (en une seule ligne):
+<code python>[
+'1100',
+'1010',
+'1001',
+'0110',
+'0101',
+'0011'
+]</code>
+\\
+Amusez-vous bien!

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page