Différences

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

--- combinaisons [2010/01/09 08:47]
tyrtamos
+++ combinaisons [2010/01/10 09:23]
tyrtamos
@@ Ligne 1: / Ligne 1: @@
 ====== Combinaisons ======
+**//En construction//**
+===== Objectif =====
+Exemple pour des combinaisons de 3 objets pris 2 à 2. Soit une liste d'objets [1,2,3]:
+  * on veut connaitre toutes les façons de les présenter 2 à 2, sans tenir compte de l'ordre: %%[[1, 2], [1, 3], [2, 3]]%%,
+  * en tenant compte si nécessaires de répétitions
+  * et on veut savoir combien  il y en a.
+NB: Contrairement aux permutations et aux arrangements, on ne tient pas compte de l'ordre: ainsi, [1, 2] et [2, 1] ne compte que pour 1.
+\\
+Référence externe pour la définition: voir [[http://fr.wikipedia.org/wiki/Combinaison_%28math%C3%A9matiques%29]] et [[http://fr.wikipedia.org/wiki/Combinaison_avec_r%C3%A9p%C3%A9tition]]
+===== Nombre de combinaisons de n objets pris k à k =====
+Le calcul du nombre de combinaisons de n objets pris k à k est donnée par la formule:
+<m>Cnk~=~{n!}/{k!(n-k)!}~=~{n(n-1)(n-2)...(n-k+1)}/{k!}</m>
+Soit, en Python (si fact(n)=factorielle de n):
+Cnk = fact(n)/(fact(k)*fact(n-k)) = n*(n-1)*(n-2)*...*(n-k+1)/fact(k)
+==== Solution non-récursive ====
+Puisque nous sommes sous Python qui sait calculer des nombres entiers énormes, nous pouvons utiliser brutalement les factorielles en prenant la fonction fact(n) présentée ailleurs sur ce site:
+<code python>
+combin = lambda n,k: fact(n)//(fact(k)*fact(n-k))
+</code>
+Il est difficile de faire plus simple...
+Mais le plus efficace est quand même le suivant, qui calcule progressivement le résultat sans calculer des grands nombres:
+<code python>
+def combin(n, k):
+    """Nombre de combinaisons de n objets pris k a k"""
+    if k > n//2:
+        k = n-k
+    x = 1
+    y = 1
+    i = n-k+1
+    while i <= n:
+        x = (x*i)//y
+        y += 1
+        i += 1
+    return x
+</code>
+Attention à ne pas utiliser dans ce code le raccourci habituel %%x *= i//y%%, car il faut que la multiplication ait lieu **avant** la division entière, sinon celle-ci ne tombe pas juste, et le résultat final est faux.
+Pour que cette fonction soit utilisable avec de très grands nombres, j'ai tenu compte des points suivants:
+  * il faut utiliser while au lieu de for, car xrange() ne supporte pas les types 'long' (en contrepartie de sa rapidité).
+  * si %%k>n//2%%, alors combin(n,k) est remplacé par combin(n, n-k) qui donne le même résultat avec moins de calculs.
+Exemple d'utilisation:
+<code python>
+print combin(3,2)  # affiche 3
+print combin(50,20)  # affiche 47129212243960
+</code>
+Ce code est très rapide: par exemple, le nombre de combinaisons de 100000 (cent mille) objets pris 100 à 100 donne en moins d'1/1000 de seconde un nombre de 343 chiffres:
+<code>
+1019745118068508355816143175813864936340849501519143871777101229221311704707028464150801159851819171048218667041957300317610197834902713500555020173048960798706784754817501032954266210951200883251987669862675631847360156537041811409331039637713779759572781307343494274990819880664139309679429703675390591419799883108282575404188096902252124000
+</code>
+==== Solution récursive ====
+La solution récursive est particulièrement simple:
+<code python>
+def combin(n,k):
+    """Nombre de combinaisons de n objets pris k a k (calcul récursif)"""
+    if k==0 or k==n:
+        return 1
+    return combin(n-1, k-1) + combin(n-1,k)
+</code>
+Malheureusement, cette solution est moins rapide que la dernière solution étudiée. De plus, elle est limitée à cause de la taille de la pile de récursion (env. 1000).
+Pour mémoire, citons une version non-récursive qui imite assez bien la version récursive en gérant directement la pile des appels:
+<code python>
+def combin(n, k):
+    """Nombre de combinaisons de n objets pris k a k (non récursif, mais imitant le récursif)"""
+    pile = [[n,k]]
+    r = 0
+    while len(pile)>0:
+        i, j = pile.pop(-1)
+        if j==0 or i==j:
+            r += 1
+        else:
+            pile.append([i-1,j-1])
+            pile.append([i-1,j])
+    return r
+</code>
+Le principe n'est pas très compliqué. On utilise une pile pour conserver les combinaisons en attente de résolution, identifiées par de simples couples de type [n,k]. La variable r, initialisée à 0, contiendra le résultat final.
+- initialement, la pile ne contient que le but à attendre: [n,k].
+- A chaque boucle while, on dépile le dernier couple [i,j]. Les 2 seuls couples dont on connait la valeur correspondent à combin(x,0), 1ère colonne du triangle de Pascal, et combin(x,x), diagonale (ou plutôt hypothénuse) du même triangle, et cette valeur est 1. Dans ce cas, on incrémente r de cette valeur et on continue. Dans les autres cas, on remplace le couple [i,j] par les 2 couples [i-1,j-1] et [i-1,j] qu'on empile.
+La boucle s'arrête quand la pile est vide! et le résultat r est renvoyé.
+Voyons cela sur un exemple. On ajoute juste après le while la ligne suivante (avec la bonne indentation):
+<code python>
+print r, pile
+</code>
+et on lance l'exemple:
+<code python>
+print combin(5,3)
+</code>
+Ce qui affiche:
+<code>
+[[5, 3]]
+[[4, 2], [4, 3]]
+[[4, 2], [3, 2], [3, 3]]
+[[4, 2], [3, 2]]
+[[4, 2], [2, 1], [2, 2]]
+[[4, 2], [2, 1]]
+[[4, 2], [1, 0], [1, 1]]
+[[4, 2], [1, 0]]
+[[4, 2]]
+[[3, 1], [3, 2]]
+[[3, 1], [2, 1], [2, 2]]
+[[3, 1], [2, 1]]
+[[3, 1], [1, 0], [1, 1]]
+[[3, 1], [1, 0]]
+[[3, 1]]
+[[2, 0], [2, 1]]
+[[2, 0], [1, 0], [1, 1]]
+[[2, 0], [1, 0]]
+[[2, 0]]
+</code>
+On voit bien que r n'est incrémentée (et la pile dépilée) que lorsque la combinaison finale est [0,x] ou [x,x].
+Le résultat final est ok, mais par rapport au code non-récursif précédent, celui-ci donne une lenteur... affligeante!
+A ne conserver que pour des considérations théoriques.
+===== Liste des combinaisons d'une liste de n objets pris k à k =====
+Nous savons maintenant calculer le **nombre** de combinaisons, nous voulons maintenant en établir la **liste**.
+Par exemple, nous voulons trouver la liste de toutes les combinaisons de de 3 objets %%[1,2,3]%% pris 2 à 2, qui est:  %%[[1,2], [1,3], [2,3]]%%
+Nous allons reprendre tout simplement le principe de "l'ensemble des parties d'un ensemble" traité dans une autre page de ce site, mais en limitant notre résultat au nombre k d'éléments voulue dans chaque partie.
+Cela donnera comme code:
+<code python>
+def combinliste(seq, 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:
+            p.append(s)
+        i += 1
+    return p
+</code>
+Exemples d'utilisation:
+<code python>
+print combinliste(['A','B','C'],2) # affiche [['A', 'B'], ['A', 'C'], ['B', 'C']]
+print combinliste(['ab','cd','ef','gh','ij'],3) # affiche [['ab', 'ef', 'ij'], ['ab', 'ef', 'gh'], ['ab', 'gh', 'ij'], ['ab', 'cd', 'gh'], ['ab', 'cd', 'ij'], ['ab', 'cd', 'ef'], ['cd', 'ef', 'gh'], ['cd', 'ef', 'ij'], ['cd', 'gh', 'ij'], ['ef', 'gh', 'ij']]
+</code>
+Comme vu précédemment, ces listes trouvées peuvent être triées.
+===== Liste des combinaisons 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 de n caractères, et qu'on cherche toutes les combinaisons des n caractères pris k à k.
+La solution la plus simple est d'utiliser la fonction précédente:
+<code python>
+def combinchaine(ch,k):
+    return [''.join(x) for x in combinliste(list(ch),k)]
+</code>
+Exemple d'utilisation:
+<code python>
+print combinchaine('ABCD',3)
+['ACD', 'ABD', 'ABC', 'BCD']
+</code>
+===== Combinaisons de n objets distincts pris k à k avec répétition =====
+Pour la théorie, voir par exemple: [[http://fr.wikipedia.org/wiki/Combinaison_avec_r%C3%A9p%C3%A9tition]]
+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, [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]]%%
+==== Nombre de combinaisons de n objets distincts pris k à k avec répétition ====
+Ce nombre est égal à la combinaison de (n+k-1) objets pris k à k.
+D'ou la fonction:
+<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>
+Exemple pour [1,2,3] pris 2 à 2 avec répétition:
+<code python>
+print combinrep(3,2)
+</code>
+==== Liste des combinaisons de n objets distincts pris k à k avec répétition ====
+On va utiliser la liste des combinaisons "normales" (sans répétition) de la façon suivante:
+  * 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]
+  * calcul de la liste des combinaisons "normales" de cette nouvelle liste comportant k*n objets pris k à k
+  * élimination du résultat des redondances de sorte que chaque séquence n'apparaisse qu'une seule fois.
+Ce qui donne comme code:
+<code python>
+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>
+==== 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 sansrepetelem(p):
+    """Supprime de la liste p toutes les séquences avec des doublons comme [1,2,2]"""
+    r = []
+    for seq in p:
+        for elem in seq:
+            ok = True
+            if seq.count(elem)!=1:
+                ok = False
+                break
+        if ok:
+            r.append(seq)
+    return r
+</code>
+Exemple:
+<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>
+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:
+\\
+Amusez-vous bien!

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page