En construction

Exemple: 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

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)

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:

combin = lambda n,k: fact(n)//(fact(k)*fact(n-k))

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:

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

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:

print combin(3,2)  # affiche 3
print combin(50,20)  # affiche 47129212243960

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:

1019745118068508355816143175813864936340849501519143871777101229221311704707028464150801159851819171048218667041957300317610197834902713500555020173048960798706784754817501032954266210951200883251987669862675631847360156537041811409331039637713779759572781307343494274990819880664139309679429703675390591419799883108282575404188096902252124000

La solution récursive est particulièrement simple:

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)

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:

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

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):

print r, pile

et on lance l'exemple:

print combin(5,3)

Ce qui affiche:

0 [[5, 3]]
0 [[4, 2], [4, 3]]
0 [[4, 2], [3, 2], [3, 3]]
1 [[4, 2], [3, 2]]
1 [[4, 2], [2, 1], [2, 2]]
2 [[4, 2], [2, 1]]
2 [[4, 2], [1, 0], [1, 1]]
3 [[4, 2], [1, 0]]
4 [[4, 2]]
4 [[3, 1], [3, 2]]
4 [[3, 1], [2, 1], [2, 2]]
5 [[3, 1], [2, 1]]
5 [[3, 1], [1, 0], [1, 1]]
6 [[3, 1], [1, 0]]
7 [[3, 1]]
7 [[2, 0], [2, 1]]
7 [[2, 0], [1, 0], [1, 1]]
8 [[2, 0], [1, 0]]
9 [[2, 0]]
10

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.

Par exemple, nous voulons trouver la liste de toutes les combinaisons de de 3 objets pris 2 à 2, qui est: [1,2,3] ⇒ [[1,2], [1,3], [2,3]]

Nous allons reprendre tout simplement le principe de “l'ensemble des parties d'un ensemble” traité plus haut. Mais en limitant notre résultat au nombre k d'éléments voulue dans chaque partie.

Cela donnera comme code:

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

Exemples d'utilisation:

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']]

Comme vu précédemment, ces listes trouvées peuvent être triées.

C'est le même principe, à part que la donnée est une chaîne de caractères, et qu'on cherche toutes les combinaisons de k caractères de cette chaîne de longueur n.

La solution la plus simple est d'utiliser la fonction précédente:

def combinchaine(ch,k):
    return [''.join(x) for x in combinliste(list(ch),k)]

Exemple d'utilisation:

print combinchaine('ABCD',3)
['ACD', 'ABD', 'ABC', 'BCD']

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:

Combin(3+2-1, 2)
6

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:

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

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:

ch = ''.join(repet(list("abcdefghijklmnopqrstuvwxyz"),2))

Amusez-vous bien!