Probleme avec le traitement de SubSequence (sous suite)
Bonsoir,
J'ai un petit sushi ... Je vous explique mon probleme. J'ai eu un dossier a rendreen python, qui portait notamment sur la generation de sous suite croissante a partir d'un liste principale. Nous avons eu la correction "Algorithmique"... C'est bien gentil mais moi sa ne m'aide pas, surtout que le python c'est nouveau. Le but du jeu est de donner la sous suite de longueur maximal.
Voici le sujet que nous avions :
Citation:
C. Suite croissante maximale
Soit (s1, ... ,sn) une liste de nombres entiers distincts. Une sous-suite croissante de nombres adjacents est appelée un run.
Dans (3,8,4,5,1,8) par exemple, la sous-suite (3,8) est un tel run. La première tâche est de trouver le ou un des runs les plus longs. --> OK
Une deuxième tâche, plus difficile, est de touver la plus longue sous-suite croissante. On ne demande plus que les éléments de la sous-suite soient adjacents dans la suite donnée. Dans l’exemple précédent, (3,4,5,8) est une sous-suite croissante.
On procède de la façon suivante : Pour le position i de 1 à n on cherche la longueur de la sous-suite maximale se terminant en si. Ces nombres satisfont la relation li = max lj + 1, où le maximum est prises parmi les indices j < i tels que sj < si.
Le maximum des nombres li est alors la longueur de la sous-suite croissante maximale. Pour trouver la sous-suite elle-même il suffit de mémoriser lors du calcul de li l’élément sj pour lequel la maximum est atteint. Executez cette idée d’abord à la main pour la rendre plus précise.
Et voici la correction donnée :
Citation:
Soit u un tableau de n nombres entiers (u[0], u[1], ..., u[n-1]) tous
distincts. Pour la fonction precedent(i) (où i est un indice compris entre 0 et n-1), dont le
résultat est j, indice de l'élément du tableau situé avant u[i] inférieur ou égal à u[i]
et le plus proche de lui. Le résultat doit être -1 si tous les élements situés avant u[i] lui
sont supérieurs. Ainsi on doit avoir (si u[i] = j est diérent de -1)
Code:
1
2
3
4
5
6
| fonction precedent(i)
j = i-1
while (j >= 0 && u[j] > u[i])
j--
#j = -1 si aucun element n'est plus petit que u[i]
return j |
Algorithme qui calcule les `i en utilisant la fonction precedent. L'algorihme affiche une suite de longueur maximale et en constituant un tableau pred des prédécesseurs de chaque ui dans une plus longue sous-suite croissante qui se termine par ui
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
ell[0] = 1
for (i = 1; i <n ; ++i)
j = precedent[i]
if (j == -1)
ell[i] = 1
pred[i] = i
else
ell[i] = ell[j] +1
pred[i] = j
for (k = j; k >= 0; k--)
if (u[k] < u[i] && ell[k] >= ell[i])
ell[i] = ell[k] +1
pred[i] = k |
On calcule ensuite le i tel que `i est maximum et on remonte de predécesseur à prédécesseur.
Code:
1
2
3
4
5
6
7
8
9
10
|
max = 0
for (i =1 ; i < n; ++i)
if (ell[i] > ell[max])
max = i
j = max
affiche(j)
while (j != pred[j])
affiche(pred[j])
j = pred[j] |
Voici ce que moi j'obtient donc de ce pseudo-code :
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
| def Max(listeT):
pred = []
liste = []
liste.insert(0,1)
for i in range(1,len(listeT)):
j = precedent(i, listeT)
#print "j = " + str(j) TEST
if (j == -1):
liste.insert(i,1)
pred.insert(i, i)
#print "pred in if = " + str(pred) TEST
else :
liste.insert(i,liste[j]+1)
pred.insert(i, j)
k = j
#print "pred in else = " + str(pred) TEST
while (k >= 0):
if (listeT[k] < listeT[i] and liste[k] >= liste[i]):
liste.insert(i,liste[k]+1)
pred.insert(i, k)
#print "pred in k = " + str(pred) TEST
k -= 1
#print "pred = " + str(pred) TEST
max = 0
for i in range(1 , len(listeT)):
if (liste[i] > liste[max]):
max = i;
j = max;
#print "j = " + str(j) TEST
while (j != pred[j]):
#print "pred[j] = " +str(pred[j]) TEST
#print "liste[j] = " +str(liste[j]) TEST
j = pred[j]
return liste
def precedent(i, listeT):
j = i-1
while (j >= 0 and listeT[j] > listeT[i]):
j = j-1
return j
listeT = [3,8,1,2,4,5,1,8]
print Max(listeT)
#resultat attendu [1,2,4,5,8] |
Si j'ai bien compris le code je suis censer recevoir la list des predecesseurs de ui. Hors je n'ai pas cela. Je n'ai pas le resultat sous les yeux. Je ne suis pas sur mon pc pour vous le donner.
De mémoire: j'obtient j = 7 --> ui index 7 = valeur 8.
Mon dernier element est donc 8. jusque la je suis content.
La taille de la sous suite aussi, j'obtient 5 en plus grande valeur. c'est ce que j'attend (tester avec plusieurs suite). Le probleme viens de la liste des predecesseurs de j.
J = 7 (valeur 8) # Ok
sont predecsseur est j = 5 (valeur 5) # Ok
le predecesseur de 5 est j = 2 (valeur 1) # AIE !
--> on est censé trouver j = 4 (si j'ai bien compris !)
Du coup ma sous suite final (reverse) est [1,5,8].
Je pense avoir un problème quand je génère la liste des prédécesseurs. Faute de ma part ou faute dans le corriger. Je n'arrive pas a savoir !
Merci a ceux qui se pencheront sur le probleme
