Warning: Undefined array key 4 in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/html.php on line 1453

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

--- arrangements [2010/01/09 08:46]
tyrtamos créée
+++ arrangements [2010/01/09 08:56]
tyrtamos
@@ Ligne 1: / Ligne 1: @@
 ====== Arrangements ======
+**//En construction//**
+Référence pour la définition: voir [[http://fr.wikipedia.org/wiki/Arrangement]]
+Par exemple, l'arrangement de 3 objets = ['A','B','C'] pris 2 à 2: %%[['B', 'A'], ['A', 'B'], ['C', 'A'], ['A', 'C'], ['C', 'B'], ['B', 'C']]%%
+Vous voyez la principale différence avec les combinaisons. Pour les combinaisons, ['B', 'A'] et ['A', 'B'] compte pour une seule solution. Autrement dit, les arrangements compteront toutes les permutations de chaque solution trouvée par les combinaisons.
+==== Calcul du nombre d'arrangements ====
+Il y a 6 arrangements, ce qui se compte de la façon suivante:
+<m>Ank~=~{n!}/{(n-k)!}~=~n(n-1)(n-2)...(n-k+1)</m>
+Ou, en Python (si fact(n) est la factorielle de n)
+Ank = fact(n)/fact(n-k) = n*(n-1)*(n-2)*...*(n-k+1)
+Ce qui donne le code suivant:
+<code python>
+def arrang(n, k):
+    """Nombre des arrangements de n objets pris k à k"""
+    if k>n:
+        return 0
+    x = 1
+    i = n-k+1
+    while i <= n:
+        x *= i
+        i += 1
+    return x
+</code>
+Exemple d'utilisation:
+<code python>
+print arrang(5,3)
+
+</code>
+Vous noterez le cas k>n qui est prévu dans la définition mathématique, sans avoir de sens physique (ex: arrangement de 3 objets pris 5 à 5 ???)
+==== Liste des arrangements  d'une liste de n objets pris k à k ====
+Comme nous savons trouver la liste des combinaisons, nous savons trouver la liste des arrangements, puisqu'à chaque combinaison trouvée correspond la liste de toutes les permutations de cette combinaison!
+Par exemple, la liste des combinaisons de 5 objets ['A','B','C','D','E'] pris 3 à 3:
+%%[['A', 'C', 'E'], ['A', 'C', 'D'], ['A', 'D', 'E'], ['A', 'B', 'D'], ['A', 'B', 'E'], ['A', 'B', 'C'], ['B', 'C', 'D'], ['B', 'C', 'E'], ['B', 'D', 'E'], ['C', 'D', 'E']]%%
+On constate que chaque combinaison trouvée est unique.
+Par exemple %%['A', 'C', 'E']%% est le seul groupement de A, C et E de toute la liste.
+Mais pour les arrangements, à ce groupement correspondra toutes les permutations de A, C et E, c'est à dire: %%['C', 'A', 'E'], ['C', 'E', 'A'], ['E', 'C', 'A'], ['E', 'A', 'C'], ['A', 'E', 'C'], ['A', 'C', 'E']%%. Idem pour toutes les autres combinaisons trouvée.
+Voici le code correspondant. Il est directement issu de combinliste(), et donc... de partiesliste():
+<code python>
+def arrangliste(seq, k):
+    """Liste des arrangements des objets de la liste seq pris k à k"""
+    p = []
+    i, imax = 0, 2**len(seq)-1
+    while i<=imax:
+        s = []
+        j, jmax = 0, len(seq)-1
+        while j<=jmax:
+            if (i>>j)&1==1:
+                s.append(seq[j])
+            j += 1
+        if len(s)==k:
+            v = permutliste(s)
+            p.extend(v)
+        i += 1
+    return p
+</code>
+Exemple d'utilisation:
+<code python>
+print arrangliste(['A','B','C'],2)  # affiche [['B', 'A'], ['A', 'B'], ['C', 'A'], ['A', 'C'], ['C', 'B'], ['B', 'C']]
+</code>
+==== Liste des arrangements d'une chaine de n caractères pris k à k ====
+C'est le même principe, à part que la donnée est une chaîne, et qu'on cherche tous les arrangements de k caractères de cette chaîne de longueur n.
+La solution la plus simple est d'utiliser la fonction précédente:
+<code python>
+def arrangchaine(ch,k):
+    return [''.join(X) for X in arrangliste(list(ch),k)]
+</code>
+Exemple d'utilisation:
+<code python>
+print arrangchaine('ABCD',3)  # affiche ['CAD', 'CDA', 'DCA', 'DAC', 'ADC', 'ACD', 'BAD', 'BDA', 'DBA', 'DAB', 'ADB', 'ABD', 'BAC', 'BCA', 'CBA', 'CAB', 'ACB', 'ABC', 'CBD', 'CDB', 'DCB', 'DBC', 'BDC', 'BCD']
+</code>
+\\
+Amusez-vous bien!
+<html>
+<head>
+<style type="text/css">
+<!--
+body {background-image:url(fondcorps.jpg);}
+-->
+</style>
+</head>
+<body>
+</body>
+</html>

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page