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 07:31]
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 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>
+\\
+Amusez-vous bien!

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page