Différences

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

--- combinaisons [2010/01/10 07:31]
tyrtamos
+++ combinaisons [2010/01/10 09:23]
tyrtamos
@@ Ligne 213: / Ligne 213: @@
 </code>
-===== Combinaisons avec répétition =====
+===== Combinaisons de n objets distincts pris k à k 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.
+Pour la théorie, voir par exemple: [[http://fr.wikipedia.org/wiki/Combinaison_avec_r%C3%A9p%C3%A9tition]]
-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.
+ici, on a n objets distincts, mais on veut les voir répétés dans les résultats des combinaisons de ces n objets pris k à k.
-Par exemple dans les combinaisons de [1,2,2] pris 2 à 2 qui donne %%[[1, 2], [1, 2], [2, 2]]%%:
+Par exemple, [1,2,3] => %%[[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]%% alors que sans répétitions: %%[[1, 2], [1, 3], [2, 3]]%%
-  * présence de séquences contenant des répétitions. Ici: [2,2]
+==== Nombre de combinaisons de n objets distincts pris k à k avec répétition ====
-  * présence de séquences identiques. Ici: [1,2] et [1,2].
+Ce nombre est égal à la combinaison de (n+k-1) objets pris k à k.
-Que peut-on faire avec ça? Tout dépendra de ce qu'on obtenir par rapport au problème à résoudre:
+D'ou la fonction:
-  * on n'a pas de répétition dans la liste des objets de départ mais on en veut dans les résultats
+<code python>
+def combinrep(n, k):
+    """Nombre de combinaisons avec répétition de n objets distincts pris k a k"""
+    return combin(n+k-1, k)
+</code>
-  * on a des répétitions dans la liste des objets de départ et on veut éliminer ses effets dans les résultats
+Exemple pour [1,2,3] pris 2 à 2 avec répétition:
-Voyons ces 2 cas.
+<code python>
+print combinrep(3,2)
+
+</code>
-**__On veut des combinaisons avec répétition__**
+==== Liste des combinaisons de n objets distincts pris k à k 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]]%%
+On va utiliser la liste des combinaisons "normales" (sans répétition) de la façon suivante:
-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].
+  * expansion de la liste initiale, de sorte que chacun des n objets soit répété k fois. Par exemple pour [1,2,3] et k=2 => [1,1,2,2,3,3]
-Combien cela va-t-il donner de séquence dans les résultats? Cela en donnera:
+  * calcul de la liste des combinaisons "normales" de cette nouvelle liste comportant k*n objets pris k à k
-<m>{C^k_{n+k-1}}</m>
+  * élimination du résultat des redondances de sorte que chaque séquence n'apparaisse qu'une seule fois.
-n étant le nombre d'objets distincts. C'est à dire:
+Ce qui donne comme code:
 <code python>
-Combin(3+2-1, 2)
+def combinlisterep(seq, k):
+    """Renvoie la liste des combinaisons avec répétition des objets de seq pris k à k"""
+    # ajoute chaque objet de seq pour quils apparaissent chacun k fois
+    seq2 = []
+    for elem in seq:
+        if elem not in seq2:
+            for i in xrange(0,k):
+                seq2.append(elem)
+    # calcule la liste "normale" des combinaisons
+    p = combinliste(seq2, k)
+    # élimine de cette liste les éléments identiques (comme [1,2] et [1,2])
+    p2 = []
+    for x in p:
+        if x not in p2:
+            p2.append(x)
+    # et renvoie le résultat
+    return p2
+</code>
+Exemple:
+<code python>
+print combinlisterep([1,2,3],2)
+[[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]
 </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:
+==== Liste des combinaisons d'une chaine de n caractères pris k à k avec répétition ====
+On va simplement utiliser la fonction précédente:
+<code python>
+def combinchainerep(ch,k):
+    return [''.join(x) for x in combinlisterep(list(ch),k)]
+</code>
+Exemple:
+<code python>
+ch = '123'
+print combinchainerep(ch,2)
+['11', '12', '13', '22', '23', '33']
+</code>
+===== Combinaisons de n objets non tous distincts pris k à k avec ou sans répétition =====
+Ici, on va généraliser tout ce qu'on a vu jusqu'à présent, pour faire à peu près tout ce qu'on veut!
+Par exemple, on a [1,2,2,3,4,4,4,5], et on va chercher les combinaisons de ces objets pris 3 à 3
+On voit qu'on a 8 objets, avec 5 objets distincts (le 2 apparait 2 fois, et le 4 apparait 3 fois).
+Le fait que certains objets se retrouvent à plusieurs exemplaires va entrainer 2 conséquences dans la liste des résultats:
+  * présence de répétitions d'éléments dans chaque séquence. Exemple: [1,2,2]
+  * présence de répétition de séquences dans la liste. Exemple: [2,4,5] et [2,4,5]
+On va donc créer du code pour, selon le problème à résoudre, supprimer des résultats l'une ou l'autre de ces répétitions (ou les 2).
+Suppression de la liste résultat des séquences comportant des répétitions d'éléments (exemple: [1,2,2])
 <code python>
-def repet(seq, m=-1):
+def sansrepetelem(p):
-    """Renvoie un liste avec chaque élément distinct de seq apparait m fois
+    """Supprime de la liste p toutes les séquences avec des doublons comme [1,2,2]"""
-       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:
+    for seq in p:
-        if elem not in r:
+        for elem in seq:
-            for k in xrange(0,m):
+            ok = True
-                r.append(elem)
+            if seq.count(elem)!=1:
+                ok = False
+                break
+        if ok:
+            r.append(seq)
     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]]%%.
+Exemple:
-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>
+p = [[1,2,2],[1,2,3],[1,1,2]]
+print sansrepetelem(p)
+[[1, 2, 3]]
+</code>
+Dans la liste résultat, suppression des séquences répétées de sorte que chaque séquence n'apparaisse qu'une seule fois (exemple: %%[[1,2,4],[1,2,4]]%% => %%[[1,2,4]]%%)
 <code python>
-ch = ''.join(repet(list("abcdefghijklmnopqrstuvwxyz"),2))
+def sansrepetseq(p):
+    """Supprime de la liste p toutes les répétitions de séquences comme [1,2,4] et [1,2,4]"""
+    r = []
+    for seq in p:
+        if seq not in r:
+            r.append(seq)
+    return r
 </code>
+Exemple:
+<code python>
+p = [[1,2,4],[1,2,3],[1,2,4]]
+print sansrepetseq(p)
+[[1, 2, 4], [1, 2, 3]]
+</code>
+On peut même supprimer les 2 type de répétitions d'un seul coup:
+<code python>
+def sansrepet(p):
+    return sansrepetelem(sansrepetseq(p))
+</code>
+On peut aussi vouloir calculer le nombre d'éléments disticts d'une séquence:
+<code python>
+def elemdiff(seq):
+    """Renvoie le nombre d'éléments différents de la liste seq"""
+    r = []
+    for elem in seq:
+        if elem not in r:
+            r.append(elem)
+    return len(r)
+</code>
+Reprenons maintenant notre exemple plus haut: seq=[1,2,2,3,4,4,4,5] et cherchons les combinaisons de ces objets non tous distincts, pris 3 à 3:

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page