Dérécursifier un calcul

Version imprimable

Bonjour,
quelqu'un voit-il la version non récursive de la fonction suivante ?

Code:

1
2
3
4
5
6
7
def combin(k,n):
    """Calcul de C(k;n) = n! / k!(n-k)! en utilisant
        C(k;n) = C(k-1;n-1) + C(k;n-1)"""
    if k==0 or k==n:
        return 1
 
    return (combin(k-1, n-1) + combin(k, n-1))

15/11/2009, 21h52
arnaudk

Salut,

Avec deux boucles imbriquées, et en construisant une liste de listes, tu as déjà essayé ?

1 pièce(s) jointe(s)

Voici la méthode que j'ai trouvée qui ne fait que des additions sur des naturels :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#!/usr/bin/env python
 
def combinaisonRecursif(k,n):
    """Calcul de C(k;n) = n! / k!(n-k)! en utilisant
        C(k;n) = C(k-1;n-1) + C(k;n-1)"""
    if k==0 or k==n:
        return 1
 
    return (combinaisonRecursif(k-1, n-1) + combinaisonRecursif(k, n-1))
 
 
def combinaisonNonRecursif(k,n):
    """Calcul de C(k;n) = n! / k!(n-k)! en utilisant
        C(k;n) = C(k-1;n-1) + C(k;n-1)
 
    Voir le document trianglePascalParColone.pdf ou trianglePascalParColone.ods (via Open Office Calc).
    Il montre comment calculer de colonnes en colonnes."""
    if k==0 or k==n:
        return 1
 
    if k==1 or k==n-1:
        return n
 
# Ici on utilise : C(n-k;n).
    test = n-k
    if k > test:
        k = test
 
    colonneInter = [0]*(n+1)
    colonne = [x for x in range(n+1)]
 
    for i in range(2, k+1):
        colonneInter[i] = 1
 
        for j in range(i+1, n+1):
            colonneInter[j] = colonneInter[j-1] + colonne[j-1]
 
        colonne = colonneInter[:] # Attention avec la copie des tableaux...
 
    return(colonne[n])
 
for n in range(11):
    for k in range(n):
        recu = combinaisonRecursif(k,n)
        nonRecu = combinaisonNonRecursif(k,n)
        if recu != nonRecu:
            print('PROBLEM POUR (k,n) = ({},{})'.format(k,n))
            print('\trecu = {}'.format(str(recu)))
            print('\tnonRecu = {}'.format(str(nonRecu)))
 
# Ce qui suit montre que la méthgode récursive est très gourmande en ressource et donc en temps...
# C'est très frappant avec des valeurs petites comme celles ci-dessous.
import time
 
k=500 # On se met dans le cas le plus défavorable pour la seconde méthode.
n=1000
 
timeStart = time.clock()
nonRecu = combinaisonNonRecursif(k,n)
timeEnd = time.clock()
print('combinaisonNonRecursif : {} s'.format(str(timeEnd - timeStart)))
print('\tnonRecu = {}'.format(str(nonRecu)))
 
import math
timeStart = time.clock()
viaFacto = math.factorial(n) // (math.factorial(k) * math.factorial(n-k))
timeEnd = time.clock()
# Programmée en C, je pense qu'elle serait plus efficace que l'utilisation des factorielles.
# Via Python, elle est plus lente mais bon la comparaison dans ce cas n'a pas de sens,
# justement parce que la factorielle est programmée en C. A VERIFIER...
print('combinaisonViaFactorielle : {} s'.format(str(timeEnd - timeStart)))
print('\tnonRecu = {}'.format(str(viaFacto)))
 
timeStart = time.clock()
nonRecu = combinaisonRecursif(k,n)
timeEnd = time.clock()
print('combinaisonRecursif : {} s'.format(str(timeEnd - timeStart)))
print('\tnonRecu = {}'.format(str(nonRecu)))

La méthode ci-dessus peut encore être optimisée en limitant au minimum la taille des colonnes utilisées : grosso modo, cela vient de ce que lorsque l'on recherche les valeurs nécessaires au calcul, on n'arrive pas forcément à la position tout en bas de la 1ère colonne. Je posterais cela ici.

Sinon ce post m'a amené au problème suivant.

Bonjour,

Puisque la formule de récurrence donnée correspond au calcul du triangle de Pascal:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 def tpascal(n): """calcul de la ligne n du triangle de Pascal""" r1 = [1,0] r2 = [1] for i in xrange(1, n+1): for j in xrange(1, i+1): r2.append(r1[j-1]+r1[j]) r2.append(0) r1 = list(r2) r2 = [1] return r1
Le calcul de la ligne n=10 du triangle de pascal calcule en fait les lignes suivantes:

Citation:

0 [1, 0]
1 [1, 1, 0]
2 [1, 2, 1, 0]
3 [1, 3, 3, 1, 0]
4 [1, 4, 6, 4, 1, 0]
5 [1, 5, 10, 10, 5, 1, 0]
6 [1, 6, 15, 20, 15, 6, 1, 0]
7 [1, 7, 21, 35, 35, 21, 7, 1, 0]
8 [1, 8, 28, 56, 70, 56, 28, 8, 1, 0]
9 [1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 0]
10 [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0]

et la combinaison cherchée est la valeur: tpascal(n)[k]. Avec n=10 et k=3, on trouve bien 120.

En ajoutant des conditions sur i et j à chaque ligne, on peut restreindre les calculs aux termes réellement utiles pour le résultat attendu.

J'ai cherché une autre solution non-récursive copiant plus fidèlement le calcul récursif (avec boucles et piles) et je n'en ai pas trouvé (dans le temps que je me suis donné).

Mais dans tous les cas, je me méfie des solutions récursives qui, en contrepartie d'un code très simple, consomme souvent beaucoup de ressources.
La meilleure méthode non récursive que j'utilise est la suivante (mais elle n'est pas basée sur la formule de récurrence donnée):
Code:

1 2 3 4 5 6 7 8 9 def combin(k,n): """combin(k,n): combinaison de n objets pris k a k""" x=1 y = 1 for i in xrange(n-k+1,n+1): x = x*i//y y += 1 return x
Attention: il ne faut pas utiliser la simplification habituelle x *= i//y, car la multiplication doit absolument être faite avant la division (sinon, celle-ci ne tombe pas juste, et le résultat est faux).

Pour de très grands nombres, il faut tenir compte des éléments suivants:
- il faut remplacer la boucle for par une boucle while
- si k>n//2 => combin(k,n) est remplacé par combin(n-k,n) qui donne le même résultat avec moins de calculs.

Avec un tel code, la combinaison de 100000 (cent mille) objets pris 100 à 100 donne en 1/10000 de secondes un nombre de 343 chiffres:

Citation:

1019745118068508355816143175813864936340849501519143871777101229221311704707028464150801159851819171048218667041957300317610197834902713500555020173048960798706784754817501032954266210951200883251987669862675631847360156537041811409331039637713779759572781307343494274990819880664139309679429703675390591419799883108282575404188096902252124000

Tyrtamos

Finalement, j'ai trouvé une solution non-récursive qui copie mieux la solution récursive avec la formule récurrente donnée:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 def combin(k, n): """Combinaison de n objets pris k a k""" pile = [[k,n]] r = 0 while len(pile)>0: j, i = pile.pop(-1) if j==0 or i==j: r += 1 else: pile.append([j-1,i-1]) pile.append([j,i-1]) 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 [k,n]. La variable r, initialisée à 0, contiendra le résultat final.

- initialement, la pile ne contient que le but à attendre: [k,n].

- A chaque boucle while, on dépile le dernier couple [j,i]. Les 2 seuls couples dont on connait la valeur correspondent à combin(0,i), 1ère colonne du triangle de Pascal, et combin(i,i), 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 [j,i] par les 2 couples [j-1,i-1] et [j,i-1] 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:

Code:

print r, pile

et on lance l'exemple:
Code:

1 2 print combin(3,5)
Ce qui affiche:

Citation:

0 [[3, 5]]
0 [[2, 4], [3, 4]]
0 [[2, 4], [2, 3], [3, 3]]
1 [[2, 4], [2, 3]]
1 [[2, 4], [1, 2], [2, 2]]
2 [[2, 4], [1, 2]]
2 [[2, 4], [0, 1], [1, 1]]
3 [[2, 4], [0, 1]]
4 [[2, 4]]
4 [[1, 3], [2, 3]]
4 [[1, 3], [1, 2], [2, 2]]
5 [[1, 3], [1, 2]]
5 [[1, 3], [0, 1], [1, 1]]
6 [[1, 3], [0, 1]]
7 [[1, 3]]
7 [[0, 2], [1, 2]]
7 [[0, 2], [0, 1], [1, 1]]
8 [[0, 2], [0, 1]]
9 [[0, 2]]
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 que j'ai donné dans mon précédent message, celui-ci donne une lenteur... affligeante!
A ne conserver que pour des raisons théoriques.

Tyrtamos

16/11/2009, 11h48
rambc

Il va falloir que j'étudie cela. Mais cela reste intéressant.

Je ne sais pas si l'utilisation de tableau dynamique apporte quelque chose. Je dis cela modulo la 2nde version que j'ai en tête qui utilisera une colonne de taille minimum.