Différences

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

--- combinatoire [2009/12/27 09:13]
tyrtamos
+++ combinatoire [2009/12/29 10:15]
tyrtamos
@@ Ligne 590: / Ligne 590: @@
 ['ACD', 'ABD', 'ABC', 'BCD']
 </code>
+==== Combinaisons avec répétition ====
+Jusqu'à présent, on a considéré que les objets dont on voulait les combinaisons, étaient tous **distincts**, c'est à dire qu'ils n'apparaissaient qu'une seul fois dans la liste (comme [1,2,3], mais pas comme [1,2,2]. Maintenant, on va voir ce qu'on peut faire avec des répétitions.
+Quand l'un des éléments au moins apparait plusieurs fois dans la liste des objets, il y a deux effets dans la liste des combinaisons.
+Par exemple dans les combinaisons de [1,2,2] pris 2 à 2 qui donne [[1, 2], [1, 2], [2, 2]]:
+  * présence de séquences contenant des répétitions. Ici: [2,2]
+  * présence de séquences identiques. Ici: [1,2] et [1,2].
+Que peut-on faire avec ça? Tout dépendra de ce qu'on obtenir par rapport au problème à résoudre:
+  * on n'a pas de répétition dans la liste des objets de départ mais on en veut dans les résultats
+  * on a des répétitions dans la liste des objets de départ et on veut éliminer ses effets dans les résultats
+Voyons ces 2 cas.
+**__On veut des combinaisons avec répétition__**
+Par exemple: on a [1,2,3], mais on veut obtenir une combinaison de ces 3 objets pris 2 à 2 **avec répétition** comme: %%[[1, 1], [1, 2], [2, 2], [1, 3], [2, 3], [3, 3]]%%
+Il suffit de transformer la liste de départ en répétant chaque élément autant de fois que la combinaison cherchée le demande (ici, 2): [1,2,3] devient donc [1,1,2,2,3,3].
+Combien cela va-t-il donner de séquence dans les résultats? Cela en donnera:
+<m>{C^k_{n+k-1}}</m>
+n étant le nombre d'objets distincts. C'est à dire:
+<code python>
+Combin(3+2-1, 2)
+</code>
+Pour calculer la liste de ces combinaisons avec répétition, on peut utiliser les fonctions sans répétition, et créer une fonction qui répète la liste de départ le nombre de fois voulu:
+<code python>
+def repet(seq, m=-1):
+    """Renvoie un liste avec chaque élément distinct de seq apparait m fois
+       si m==0, renvoie seq sans rien changer
+       si m==-1 (défaut), chaque élément de seq apparait len(seq) fois
+    """
+    if m == 0:
+        return seq[:]
+    if m == -1:
+        m = len(seq)
+    r = []
+    for elem in seq:
+        if elem not in r:
+            for k in xrange(0,m):
+                r.append(elem)
+    return r
+</code>
+Avec cette fonction, la liste d'objet seq=[1,2,3] devient avec seq2=repet(seq,2): [1,1,2,2,3,3]. Et combinliste(seq2,2) donne la liste voulue: %%[[1, 1], [1, 2], [2, 2], [1, 3], [2, 3], [3, 3]]%%.
+On peut faire la même chose avec une chaine de caractère. Par exemple, on veut la liste des mots de 3 lettres de l'alphabet, chaque lettre ne pouvant être répété que 2 fois:
+<code python>
+ch = ''.join(repet(list("abcdefghijklmnopqrstuvwxyz"),2))
+</code>
 ===== Arrangement =====

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page