Discussion :

[Aigaio]

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 :

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 :

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[VinsS]

Salut,

Je me suis perdu dans tes explications pour la première partie, par contre, pour la fonction precedent(), je pense que ceci répond à tes attentes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
def precedent(i, lst):
    return max([x for x in lst[:i] if x <= lst[i]])

Ça donne ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
listeT = [3,8,1,2,4,7,1,8]
print precedent(3, listeT)
print precedent(4, listeT)
print precedent(5, listeT)
print precedent(6, listeT)
print precedent(7, listeT)

vincent@tiemoko:~/Bureau$ python prec.py
1
3
4
1
8

Ooops, j'avais oublié qu'il fallait retourner -1 si le nombre était plus petit que tous ses précédents, alors ceci sera mieux:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
def precedent(i, lst):
    nb = [x for x in lst[:i] if x <= lst[i]]
    if nb:
        return max(nb)
    return -1

[seb2991]

Salut vincent,

en fait notre problème n'est pas la fonction précédent, elle marche très bien !!!

Ce qu'il nous faut en fait, c'est pouvoir trouver la sous suite croissante maximale de la liste listeT

[VinsS]

Salut,

Voyons si la nuit m'a porté conseil:

Est-ce que ceci fait l'affaire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#!/usr/bin/env python 
# -*- coding: UTF-8 -*-
 
def extract_sublist(lst):
    results = []
    for i in range(2, len(lst)):
        results.append(get_precedents(i, lst))
    for idx, r in enumerate(results):
        print "{0}: {1}".format(idx, r)
 
def get_precedents(i, lst):
    s = set([x for x in lst[:i] if x <= lst[i]])
    if s:
        return sorted(list(s))
    return -1
 
listeT = [3,8,5,2,4,7,1,8]
extract_sublist(listeT)

vincent@tiemoko:~/Bureau$ python prec.py
0: [3]
1: -1
2: [2, 3]
3: [2, 3, 4, 5]
4: -1
5: [1, 2, 3, 4, 5, 7, 8]

Donc, on commence par le troisième élément puisque les deux premiers n'ont pas de sous-suite.

Ici le code affiche la plus grande sous-suite pour chaque valeur de la liste,
je te laisse ajouter la ligne de code pour sélectionner la plus longue.

Si ta liste de départ est aléatoire, ne perd pas de vue que tu peux avoir plusieurs solutions valables.