Liste de listes avec compteur

Version imprimable

Bonjour,
je débute en python et je dois créer un script déterminant les meilleurs alignements possibles entre deux séquences.
J'ai créé une matrice de coût selon une distance donnée: je la remplis en partant du coin supérieur gauche en allant vers le coin inférieur droit.
Jusqu'à ce point, pas de problème;)
Pour la suite, il faut que je "remonte" en partant du coin inférieur droit jusqu'au supérieur gauche en affichant les meilleurs alignements:
si je suis en (i,j) je regarde en (i-1,j) (i, j-1) et (i-1, j-1) et je prends les plus petits que je stocke dans une (des) liste(s).
Je veux créer une liste contenant toutes les listes qui vont se créer et se modifier à chaque tour:

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
79
80
81
82
83
84
85
86
87
88
89
90
from Matrice_Cout import *
from Levenshtein import *
from copy import *
 
compteur = 0
 
 
def Alignement(x, y, i, j, T, L):
    """Prend en entrée les deux séquences à aligner,
    la matrice des couts,
    et la position actuelle dans la matrice des couts
    (ligne i, colonne j) 
    Sortie: liste de listes des alignements optimaux des séquences"""
 
    """if i != 1:
        if j != 1:
            if T[i, j] == T[i-1,j-1] + Sub(x[i-2], y[j-2]):
                Alignement(x, y, i-1, j-1, T)
            elif T[i, j] == T[i-1, j] + Del(x[i-2]):
                Alignement(x, y, i-1, j, T)
            else:
                Alignement(x, y, i, j-1, T)
        else:
            Alignement(x, y, i-1, 1, T)
    else:
        if j != 1:
            Alignement(x, y, 1, j-1, T)"""
 
    c = [0]*3
 
    #Copie de L
    M =  deepcopy(L) 
 
    if i != 1:
        if j != 1:
            if T.getitem(i, j) == T.getitem(i-1,j-1) + Sub(x[i-2], y[j-2]):
                c[0] = 1
                L = M + [[x[i-2], y[j-2]]]
                Alignement(x, y, i-1, j-1, T, L)
                print L
                print "ok1"
            elif T.getitem(i, j) == T.getitem(i-1, j) + Del(x[i-2]):
                c[1] = 1
                if sum(c) == 1:
                    L = M + [[x[i-2], '-']]
                    Alignement(x, y, i-1, j, T, L)
                    print L
                else:
                    compteur += 1
                    L[compteur] = M + [[x[i-2], '-']]
                    Alignement(x, y, i-1, j, T, L[compteur])
                    print L[compteur]
            else:
                c[2] = 1
                if sum(c) == 1:
                   L = M +  [['-', y[j-2]]]
                   Alignement(x, y, i, j-1, T, L)
                   print L
                   print "ok2"
                elif sum(c) == 2:
                    compteur += 1
                    L[compteur] = M + [['-', y[j-2]]]
                    Alignement(x, y, i, j-1, T, L[compteur])
                    print L[compteur]
                    print "ok3"
                else:
                    compteur += 1
                    L[compteur] = M + [['-', y[j-2]]]
                    Alignement(x, y, i, j-1, T, L[compteur])
                    print L[compteur]
        else:
            L = M + [[x[i-2], '-']]
            Alignement(x, y, i-1, 1, T, L)
            print L
    else:
        if j != 1:
            L = M +  [['-', y[j-2]]]
            Alignement(x, y, 1, j-1, T, L)
            print L
    return M
 
 
if __name__ == "__main__":
    seq1 = 'YWCQPGK' 
    seq2 = 'LAWYQQKPGKA'
    m = len(seq1)
    n = len(seq2)
    T = Matrice_cout(seq1, seq2)
    L = Alignement(seq1, seq2, m+1, n+1, T, [])
    print L

Cela ne fait pas du tout ce que je veux.:cry:
Quelqu'un aurait une piste, svp?
Merci d'avance :D

Bonjour,
Je ne suis pas sûr de bien comprendre ce que tu veux faire et je ne suis pas très fort en math, mais je pense que tu peux regarder du coté de numpy, c'est pratique pour gérer des matrices.
Je ne crois pas que ce soit ce que tu veux mais voici un exemple:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import numpy #matrice de depart matrice = numpy.array([(5,2,1,4), (2,3,8,9), (5,3,5,8), (1,0,8,7)]) #matrice du resultat matriceOut = numpy.zeros((matrice.shape)) #recopie la ligne 0 et la colonne 0 dans la matrice resultat matriceOut[0, :] = matrice[0, :] matriceOut[:, 0] = matrice[:, 0] #boucle la matrice for i in range(1, matrice.shape[0]): for j in range(1, matrice.shape[1]): #stock le resultat matriceOut[i, j] = min(matrice[i-1, j], matrice[i, j-1], matrice[i-1, j-1]) print matrice print matriceOut

problème sur la récursivité

Bonjour,
tout d'abord, merci Nyko77: je ne connaissais pas, je m'en servirais peut-être :ccool:
Malheureusement, cela ne répond pas à ma question qui est sûrement très confuse :oops:
En fait, en arrangeant le code, j'ai la sortie que je veux mais ce n'est pas très "propre".
En effet, pour :

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
compteur = 0
 
def Alignement(x, y, i, j, T, L):
    """Prend en entrée les deux séquences à aligner,
    la matrice des couts,
    et la position actuelle dans la matrice des couts
    (ligne i, colonne j) 
    Sortie: liste de listes des alignements optimaux des séquences"""
 
    global compteur
    c = [0]*3
    maxi=max(len(x), len(y))
 
    #Copie de L
    M =  deepcopy(L) 
 
    if i != 1:
        if j != 1:
            if T.getitem(i, j) == T.getitem(i-1,j-1) + Sub(x[i-2], y[j-2]):
                c[0] = 1
                L = M + [[x[i-2], y[j-2]]]
                Alignement(x, y, i-1, j-1, T, L)
                if len(L)==maxi:
                    print L[::-1]
            if T.getitem(i, j) == T.getitem(i-1, j) + Del(x[i-2]):
                c[1] = 1
                if sum(c) == 1:
                    L = M + [[x[i-2], '-']]
                    Alignement(x, y, i-1, j, T, L)
                    if len(L)==maxi:
                        print L[::-1]
                else:
                    compteur += 1
                    L[compteur] = M + [[x[i-2], '-']]
                    Alignement(x, y, i-1, j, T, L[compteur])
                    if len(L[compteur])==maxi:
                        print L[compteur][::-1]
            if T.getitem(i, j) == T.getitem(i, j-1) + Ins(y[i-2]):
                c[2] = 1
                if sum(c) == 1:
                   L = M +  [['-', y[j-2]]]
                   Alignement(x, y, i, j-1, T, L)
                   if len(L)==maxi:
                       print L[::-1]
                elif sum(c) == 2:
                    compteur += 1
                    L[compteur] = M + [['-', y[j-2]]]
                    Alignement(x, y, i, j-1, T, L[compteur])
                    if len(L[compteur])==maxi:
                        print L[compteur][::-1]
                else:
                    compteur += 1
                    L[compteur] = M + [['-', y[j-2]]]
                    Alignement(x, y, i, j-1, T, L[compteur])
                    if len(L[compteur])==maxi:
                        print L[compteur][::-1]
        else:
            L = M + [[x[i-2], '-']]
            Alignement(x, y, i-1, 1, T, L)
            if len(L)==maxi:
                print L[::-1]
    else:
        if j != 1:
            L = M +  [['-', y[j-2]]]
            Alignement(x, y, 1, j-1, T, L)
            if len(L)==maxi:
                print L[::-1]
    return M
 
 
if __name__ == "__main__":
    seq1 = 'YWCQPGK' 
    seq2 = 'LAWYQQKPGKA'
    m = len(seq1)
    n = len(seq2)
    T = Matrice_cout(seq1, seq2)
    L = Alignement(seq1, seq2, m+1, n+1, T, [])

j'ai L=[] à la fin, alors qu'il me semble que je le remplis :mur:
Je dois passer à côté de la récursivité...
Si quelqu'un pouvait, svp, m'expliquer pourquoi lorsque je remplis une liste, les sorties "au fur et à mesure" sont correctes mais en ordre inversé (par rapport à ma logique)?
Merci d'avance :D

09/03/2010, 09h49
eyquem

Bonjour,

Pourrais tu donner de l'information permettant de faire tourner ton code stp.
Il manque au moins la connaissance de la matrice des coûts de départ pour cela.