Combinaison sans répétitions

by dinosaure

Dans un de mes programmes, j’ai dût faire un petit sous programme qui fait des combinaisons sans répétions. En effet, il fallait faire toutes les combinaisons possibles sans prendre en compte l’ordre de celles-ci. Par exemple, ["A","B","C"] équivaut à ["B","C","A"]. J’ai donc d’abord appliqué mes idées en Python (histoire d’éviter le compilation en C++). Je me suis référer à Wikipédia et j’ai demandé de l’aide à certaines personnes sur Progmod pas pour me donner un code déjà tout fait mais pour me donner un petit coup de pouce. Il fallait que je parte sur quelque chose de solide.

La première chose à savoir sur la combinaison sans répétitions, c’est ceci: . Cette formule mathématique détermine le nombre de combinaisons possibles qu’il peut y avoir avec n la taille de l’alphabet et k la taille d’une combinaison. Par exemple, si nous devions choisir 5 nombres différents entre 1 et 50, nous aurions: possibilités. Ce calcul est important pour notre programme et il nous suffira d’implémenter une fonction factorielle pour avoir le résultat.

Ensuite, il faut voir le lien possible avec les combinaisons, et là, c’est à l’aide d’un exemple que l’on peut s’en sortir. Pour un alphabet ["A","B","C","D","E"], on veut toutes les combinaisons à 3 éléments:

  • EAB
  • EAC
  • EAD
  • EBC
  • EBD
  • ECD
  • DAB
  • DAC
  • DBC
  • ABC

Bon il suffit de ce triturer un peu la tête pour obtenir ce résultat et dans ce cas ci, je vous ais ranger les combinaisons selon un ordre qui vous aidera à établir l’algorithme. Comme on peut le constater, cette liste ce compose en 3 grandes parties, les combinaisons contenant la lettre E, les combinaisons contenant la lettre D et la seul combinaison sans répétitions de 3 éléments possible pour l’alphabet ["A","B","C"]. On peut partir du constat donc que toutes les combinaisons d’un alphabet ["A","B","C","D","E"] équivaut à toutes les combinaisons d’un alphabet ["A","B","C","D"] plus toutes les combinaisons possibles contenant la lettre E. Ou plus généralement, l’ensemble des combinaisons parmi les 1..N, c’est l’union des combinaisons parmi les 1..N-1 (donc qui ne contiennent pas N), et des combinaisons qui contiennent N avec N la taille de notre alphabet.

Ceci fait référence à quoi au final ? À la récursivité ! Et oui, on pourrait présenter ce problème comme ceci:

L.pop() // On enlève la dernière lettre
G = G + combinaisons(L, k) // On fait l'union des combinaisons 
                              parmi les L[1]..L[N-1] et 
                              des combinaisons qui contiennent L[N]

L étant notre alphabet, G le résultat que nous recherchons et k la taille d’une combinaisons. Au final, il s’agit maintenant de faire seulement toutes les combinaisons possibles contenant L[N]. Mais attention, nous avons repérer un cas particulier. En effet, si k (la taille d’une combinaison) équivaut à la taille de notre alphabet L, on peut déduire que la seul combinaisons dans ce cas et directement L (en effet, on peut le voir avec la dernière combinaison de notre exemple: « ABC »). Il y a 2 autres cas que nous devons traiter avant d’attaquer le gros morceau.

En effet, si notre k équivaut à 1, alors, il suffit de retourner comme valeur les éléments qui compose L. Par exemple, si on veut toutes les combinaisons contenant 1 seul élément (k) pour un alphabet ["A","B","C"], nous aurons comme résultat, ceci:

  • A
  • B
  • C

Et le deuxième cas est l’impossibilité de faire toutes les combinaisons sans répétitions. Il nous est impossible de faire les combinaisons contenant 4 éléments pour un alphabet n’en contenant que 3. Ce cas est possibles seulement dans le cadre de combinaisons avec répétitions.

On peut maintenant mettre en forme notre application déjà en traitant nos 3 cas:

def combinaisons(L, N, k):
    i = 0

    G = []
    s = ""

    if len(L) < N: # L'impossibilité
        return G
    elif N == 1: # Si k = 1
        return L
    elif len(L) == N: # Si k équivaut à la taille de notre alphabet
        while i < len(L)
            s = s + L[i]
            i = i + 1

        G.append(s)

    return G

Bon, ce code est du Python, je pense que c’est un langage qui est compréhensible par tout ceux qui ont des bases en programmation. Mais attention, la notation est un peu plus différente que ce qu’on a vue précédemment. Dans ce code, k représente le rang mais c’est un détail que nous verrons plus tard. Il faut bien comprendre ici que N équivaut à la taille d’une combinaison et L est notre alphabet.

Maintenant, il s’agit de faire toutes les combinaisons avec la dernière lettre de notre alphabet. Dans notre exemple, c’est E:

  • EAB (5 1 2)
  • EAC (5 1 3)
  • EAD (5 1 4)
  • EBC (5 2 3)
  • EBD (5 2 4)
  • ECD (5 3 4)

Là aussi, il faut remarquer un cheminement logique entre les combinaisons. J’ai mis des nombres à côté pour que ce soit plus parlant, il faut juste comprendre que l’alphabet ["A","B","C","D","E"] équivaut à l’alphabet [1,2,3,4,5]. Et la, normalement, ça saute aux yeux. En effet, on incrémente le dernier élément de notre dernière combinaison mais si, celui-ci équivaut au dernier élément de notre alphabet, alors on incrémente l’avant dernier élément de notre dernière combinaison.

  • EAB = L[4] + L[0] + L[1]
  • EAC = L[4] + L[0] + L[2]
  • EAD = L[4] + L[0] + L[3] // 3 = 4 - 1
  • EBC = L[4] + L[1] + L[2]
  • EBD = L[4] + L[1] + L[3] // 3 = 4 - 1
  • ECD = L[4] + L[2] + L[3]

Autre remarque que l’on peut faire, c’est que si on enlève la lettre E de nos combinaisons, on a toutes les combinaisons possibles contenant 2 éléments pour l’alphabet ["A","B","C","D"]. On peut donc définir que ce nombre de combinaisons équivaut à: avec 4, la taille de notre alphabet moins 1 et 2, la taille d’une combinaison moins 1 ! On pourrait implémenter ce mécanisme de façon itérative (c’est à dire, à l’aide d’une boucle) donc la valeur maximal serait le résultat de notre formule mathématique.

L’idée donc serait de créer un tableau n qui contiendrait les différents curseurs de notre alphabet. Dans notre exemple n[0] équivaudrait à 0 pour notre première combinaison et n[1] serait égal à 1. Ensuite n[0] ne changera pas et n[1] sera incrémenter pour être égal à 2 pour notre deuxième combinaison. Et dans le cas où n[1] serait égal à la taille de notre alphabet, alors on incrémentera la valeur précédente du tableau n. Seulement, il faut s’intéresser au cas général et cette technique ce trouver limiter par le nombre d’élément dans une combinaison (ici 3). Il faut aussi dénoter que la taille du tableau n dépend de la taille d’une combinaison (comme il en est le curseur) mais comme le premier élément de nos combinaisons n’est pas important (il reste le même), la taille du tableau n équivaudra à N - 1 dans notre code.

C’est là où intervient la notion de rang. Dans ce cas ci, nous avons ce qu’on appelle 3 rangs. Le rang contenant la lettre E au début, le rang contenant la lettre D au début et le dernier rang qui est un cas particulier. Mais le rang ne nous permet pas que de savoir cela, il nous permet de savoir aussi à quelle valeur doit s’arrêter nos curseurs dans le tableau n. En effet, n[0] doit s’arrêter à la troisième valeur de notre alphabet et n[1] à la quatrième. Cela ce repère facilement quant il s’agit de faire des combinaisons à 4 éléments (ce que je vous invite à faire pour mieux comprendre).

Enfin, il faut souligner aussi une dernière notion qui est de bien comprendre que la première valeur d’une liste ou d’un tableau en programmation, c’est tableau[0] et pas tableau[1]. C’est peut être anodin mais j’utilise des notions comme 3 ou 4 où il faudrait, dans notre programmation, soustraire par 1.

On peut donc commencer un peu à coder après avoir mis toutes les idées en place. Nous nous positionnons directement dans le cas où nous devons faire une combinaisons, c’est à dire quand la taille de notre combinaison et strictement inférieur à la taille de notre alphabet:

l = factorielle(len(L) - 1)/(factorielle(N - 1)
     * factorielle((len(L) - 1) - (N - 1)));

Ici, il s’agit de calculer la limite de notre boucle pour générer de façon itérative nos combinaisons. Comme on l’a constater pour générer les combinaisons avec la lettre E, nous avons à appliquer la formule: où, je le rappelle 4 est la taille de notre alphabet (len(L)) moins 1 et 2, la taille d’une combinaison (N) moins 1.

while i < l:
    s = L[len(L) - 1]

On sait que nos combinaisons commencerons toujours par la dernière lettre de notre alphabet (ici E). Note tout de même que j’enregistre les combinaison dans une variable de type String. J’aurai pu enregistrer les combinaisons dans une liste, ce n’est pas très compliqué (c’est notamment ce que j’ai fait en C++) mais la variable de type String me suffit amplement.

    while h < len(n):
        if j > 0 and j < len(n):
            n[j] = n[j - 1] + 1

        s = s + L[n[h]]
        h = h + 1
        j = j + 1

C’est là où ça devient un peu compliqué. Comme on peut le remarquer, on utilise 2 nouvelles variables j et h. Il faut comprendre ici, que, quand i = 0, c’est à dire dès notre première combinaison, j et h sont aussi égal à 0. Néanmoins la variable j et tout aussi importante car elle permet de mémoriser quelle curseur a été modifié auparavant. Pour la première combinaison, il est logique que j ne renvoi à aucune valeur cependant, pour, par exemple, la deuxième combinaison, j permettra de nous dire que la dernière valeur de notre tableau n (contenant nos curseurs) a été modifié. C’est important de pouvoir dénoter ça car, dans le cas d’une génération de combinaisons avec 4 éléments ainsi que le même alphabet, j nous dira que ce serait (dans un des cas) l’avant l’avant dernière valeurs de notre tableau n qui a été modifié. L’intérêt ensuite est d’incrémenter toutes les valeurs du tableau n après j pour qu’on est un ensemble cohérent. En effet:

  • EAD = L[4] + L[0] + L[3] // L[4] + L[ n[0] ] + L[ n[1] ]
  • EBC = L[4] + L[1] + L[2]

Quand on arrive au maximum (ici D) possible pour le dernier élément de notre combinaison, on a vue qu’on modifiait l’avant dernière valeur de n. Cependant, on peut remarquer tout de même que la dernière valeur de n est elle aussi modifié ! Et elle n’équivaut pas à une soustraction de 1 de son ancienne valeur (2 = 3 - 1) car, si vous avez le cas d’une combinaison à 4 éléments avec le même alphabet, vous auriez remarquer que le tableau n est une suite récurrente n[j+1] = n[j] + 1 dont la valeur initial (et c’est important de le spécifié) et n[j]. Cette exemple montre aussi qu’on est capable d’implémenter quelque chose de récurrent de façon itérative (à l’aide d’une boucle). Mais revenons à nos moutons. Comme vous pouvez le remarquer, à l’initialisation quand i = 0, le tableau n équivaut au début à cela: [0,0] (n’oubliez pas que la taille du tableau n équivaut à la taille d’une combinaison moins 1), après passage de la deuxième boucle, il aura comme valeur ceci: [0,1] et si on ce réfère à la notre quatrième liste d’exemples, on peut retrouver que la première combinaison équivaut à EAB = L[4] + L[0] + L[1], donc dans notre cas à EAB = L[4] + L[ n[0] ] + L[ n[1] ]. Remarque tout de même que je rajoute immédiatement les valeurs dans la combinaison dans la boucle avec s = s + L[n[h]] et ensuite, je fais une incrémentation de h et de j.

Ensuite, il peut être déroutant de ce voir utiliser la variable j dans la boucle alors que la variable qui arrêtera la boucle est h. Mais j intervient seulement pour réinitialiser le tableau n selon la suite récurrente que l’on vient de voir. Mais l’intérêt de j s’explique véritablement après, quand il s’agit de savoir quelle valeur de n nous devons commencer à modifier.

    h = 0
    j = 0

    while j < len(n) and n[j] != j + k:
        j = j + 1

    if j > 0:
        n[j - 1] = n[j - 1] + 1

    i = i + 1

Voilà le grand intérêt de j.D’abord, il faut remarquer une chose, c’est que la variable j n’est pas remis à 0 pour la boucle suivante (ce qui est le cas de h), car la valeur qu’on a trouver de j nous servira pour le passage dans la boucle suivant. Là où c’est réellement intéressant, c’est dans la deuxième boucle où la condition est bien particulière j < len(n) and n[j] != j + k. Il y a deux choses à repérer. Déjà, il faut que j soit strictement inférieur à la taille de notre tableau n (car si on ce réfère au code précédent, si j et supérieur ou égal à la taille du tableau n, il y aura une erreur puisqu’on utilise n[j]) et ensuite, il faut que n[j] soit différent de j + k. Il faut revenir en arrière pour comprendre un peu le pourquoi de cette condition. On a en effet, dit que la dernière valeur de notre tableau n dans le cas d’une combinaison à 3 éléments ne doit pas dépasser 3 car L[3] équivaut à D et si on dépasse 3, on ce retrouve à rajouter la lettre E à la prochaine combinaison ce que nous ne voulons pas faire. Cependant, il faut aussi savoir que l’avant dernière valeur de notre tableau n ne doit pas dépasser 2 (c’est à dire la lettre C). Cette explication ce voit plus particulièrement quant il s’agit de faire une combinaison à 4 éléments. Ainsi, à l’aide de cette boucle, si l’un de nos curseurs (une des valeurs de notre tableau n) équivaut à sa limite (D ou C selon le curseur), on arrête d’incrémenter j. j pointera sur une des valeurs du tableau n qui est à son maximum ! Notez tout de même qu’il y a un certain sens à prendre en compte. On pourrait très bien aussi prendre le curseur qui est à son maximum en partant de la fin mais si le suivant est aussi à son maximum (toujours en partant de la fin), j ne pointera pas vers celui-ci et nous aurons une erreur. Le fait est que nous devons avoir le premier curseur qui en est à son maximum en partant du début. Après cela, on a juste à incrémenter le curseur précédent à j de 1. On peut encore une fois voir ce fait dans une liste:

  • EAD, n[1] = 3, c'est le maximum
  • EBC, on incrément n[0] de 1

On peut aussi noter la notion de rang qui est primordiale car c’est grâce à lui et à j qu’on détermine le maximum par la formule: j + k. Et après qu’on a déterminer j on refait une réinitialisation de n avec comme valeur initial n[j]. C’est bien à prendre en compte car dans une combinaisons de 4 éléments avec le même alphabet, j pourrait être égal à 1 alors que la première valeur du tableau n est n[0]. Donc la valeur j est essentiel pour que les curseurs ont une suite logique. Au final, votre code doit ressembler à cela:

L = ["A","B","C","D","E"]
N = 4
G = []

def factorielle(x):
    if x < 2:
        return 1
    else:
        return x * factorielle(x - 1)

def combinaisons(L, N, k):
    h = 0
    i = 0
    j = 0

    n = [0] * (N - 1)

    G = []
    s = ""

    if len(L) < N:
        return G
    elif N == 1:
        return L
    elif len(L) == N:
        while i < len(L):
            s = s + L[i]
            i = i + 1

        G.append(s)
    elif len(L) > N:
        l = factorielle(len(L) - 1)/(factorielle(N - 1)
             * factorielle((len(L) - 1) - (N - 1)));

        while i < l:
            s = L[len(L) - 1]

            while h < len(n):
                if j > 0 and j < len(n):
                    n[j] = n[j - 1] + 1

                s = s + L[n[h]]
                h = h + 1
                j = j + 1

            G.append(s)

            h = 0
            j = 0

            while j < len(n) and n[j] != j + k:
                j = j + 1

            if j > 0:
                n[j - 1] = n[j - 1] + 1

            i = i + 1

        L.pop()
        G = G + combinaisons(L, N, k - 1)

    return G

G = combinaisons(L, N, len(L) - N)

print(G)

Notez tout de même l’ajout à la fin de L.pop() et G = G + combinaisons(L, N, k - 1) qu’on a expliquer au début de cette article. Il faut noter aussi que la fonction combinaisons reçoit 3 paramètres. Le paramètre en plus est le rang k. Et le dernier rang possible pour des combinaisons de 3 éléments pour un alphabet de 5 éléments et 2 car:

  • Deuxième rang: combinaisons contenant la lettre E
  • Premier rang: combinaisons contenant la lettre D
  • Le cas particulier ABC

Bon voilà, les combinaisons sans répétions, c’est compliqué … Sérieusement, cela nous permet d’appréhender d’autres problèmes qui peuvent être typique de celui-ci, le mieux c’est de trouver tout seul les rapports logiques qu’il peut y avoir entre les combinaisons et ensuite d’appliquer nos idées en terme de programmation (à l’aide de Python notamment) et c’est comme ça qu’on avance. C’est sûr, vous n’y arriverez pas du premier coup, j’ai mis un certains temps avant de trouver cette algorithme et je suis sûr, il existe encore un moyen plus rapide que celui-ci néanmoins, l’intérêt c’est justement de comprendre et d’apprendre. On ne vous demande pas de tout savoir, pour preuve, on est aller chercher certaines notions sur Wikipédia, on vous demande d’être avant tout logique et grâce à ça, vous pouvez voir le lien possible qu’il y a entre certains éléments et par la suite les générer.