Forum de mathématiques - Bibm@th.net

Marie-Josephe

Invité

[Python]Plus longue sous-suite croissante

Bonjour,

Je dois coder en Python un programme qui prend en entrée un tableau u non trié de longueur n et qui me renvoie la plus longue sous-suite croissante. Voici le sujet :

Pour tout i ∈ [0, n − 1], on note [tex]m_i[/tex] la longueur maximale des sous-suites croissantes de u dont le dernier terme est [tex]u_i[/tex]
a. Programmer une fonction tabLongueurMax(u) qui calcule [tex]m_0[/tex], ..., [tex]m_{n-1}[/tex] de proche en proche (et les renvoie sous forme d’un tableau). En déduire une fonction longueurMax(u) déterminant la longueur maximale des sous-suites croissantes de u.
[tex]b.[/tex] À l’aide des fonctions précédentes, écrire une fonction plssc(u) qui détermine une plus longue sous-suite croissante de u.

J'ai réussi à coder les deux programmes demandés par la question a) , mais je ne sais pas comment les utiliser pour obtenir la plus longue sous-suite croissante... Si vous aviez une idée, pas nécessairement en langage python mais juste l'idée de l'algorithme... merci d'avance !

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : [Python]Plus longue sous-suite croissante

Bonjour,

Je suppose que pour i de 0 à n-1 vous avez rangé les i tels que [tex]u_i > u_{1+1}[/tex] (> ou =)
Reste à exploiter les différences entre les i rangés successivement : Ce sont les[tex] m_i[/tex]
La plus grande différence correspond à la plus longue sous-suite croissante…et vous en avez les deux bouts
Ai-je bien compris le problème ?

Dernière modification par totomm (29-12-2013 17:48:50)

Marie-Josephe

Invité

Re : [Python]Plus longue sous-suite croissante

Bonjour,

Ben non justement, les u_i ne sont PAS triés pas ordre croissant

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : [Python]Plus longue sous-suite croissante

Bonjour,

Je suis navré que mon commentaire n'ait pas été assez clair.
yoshi est un bon connaisseur de Python, Son intervention serait bonne pour améliorer ou compléter les programmes qui seraient montrés.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : [Python]Plus longue sous-suite croissante

Bonjour,

Le "bon" connaisseur de Python serait bien déjà intervenu s'il comprenait de quoi il retourne...
Or, la lecture de l'énoncé me laisse perplexe :

Pour tout i ∈ [0, n − 1], on note [tex]m_i[/tex] la longueur maximale des sous-suites croissantes de u dont le dernier terme est [tex]u_i[/tex]

Qu'est-ce que le tableau u ? Que contient-il ? sa définition existe-t-elle ? Que contient-il au juste ?
Au passage, pour utiliser des tableaux en Python, il faut faire appel au module numpy, sinon, ce sont des listes...
Que sont des sous-suites d'une liste ? Jamais entendu ce terme...
Comment aurais-je pu répondre à quelqu'un qui a passé le cap de la 1ere question, alors que je ne comprends même pas de quoi on y parle, donc qui est meilleur que moi  ?

Peut-être que la suggestion - à demi-mot - de totomm de poster les programmes déjà écrits permettrait de faire un peu de lumière ?

@+

[EDIT]
Si j'ai une liste L, non triée, composée de n éléments numériques, je peux en extraire le grand le plus petit sans écrire de fonctions supplémentaires via les fonctions natives max() et min() :

>>> L=[1,0,-1,7,20,4,3,5]
>>> max(L),min(L)
(20, -1)
>>>

Mais cela ne fait pas avancer le schmilblick comme disait Coluche...

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : [Python]Plus longue sous-suite croissante

rebonjour,

merci yoshi pour les questions que j'aurais dû poser, je m'étais fait un petit exemple "a priori" :

u : [1,3,4,2,5,7,9,2,3]
i :   0,1,2,3,4,5,6,7,8

3 sous-suites croissantes :
[1,3,4] de début i=0 et de longueur 3
[2,5,7,9] de début i=3 et de longueur 4
[2,3] de début i=7 et de longueur 2

Cela est-il bien conforme au problème à programmer ?

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : [Python]Plus longue sous-suite croissante

Ave,

Ah...
La liste u contiendrait donc une suite de nombres... entiers ? naturels ? relatifs ? nombres décimaux ? Autre chose ?
Conditionné, j'avais interprété suites comme les Suites arithmétiques, géométriques, récurrentes...
Cela n'aurait donc rien à voir ?

@+

Marie-Josephe

Invité

Re : [Python]Plus longue sous-suite croissante

Oui c'est ça, ce sont des tableaux contenant des entiers naturels dans le desordre
Par exemple, on prend le tableau "u" : [2,0,1,5,4,6,7,3]
Alors la plus longue sous-suite croissante est [0,1,4,6,7].
Le programme tabLongueurMax me renvoie [1, 1, 2, 3, 3, 4, 5, 3] qui regroupe les valeurs de m (qui sont la longueur de la plus longue sous-suite terminant à cet indice). Puis longueurMax renvoie alors 5.

Ainsi avec ces deux fonctions, je connais:
- La longueur de la plus longue sous-suite croissante
- L'indice à laquelle termine cette plus longue sous-suite

Et maintenant j'aimerais connaître à partir de ces informations la dite plus longue sous-suite. J'espère avoir été clair..

Marie-Josephe

Invité

Re : [Python]Plus longue sous-suite croissante

Voici une partie de l'énoncé que j'aurais dû copier :

On considère une suite finie (un tableau) [tex]u = [u_0, u_1, ..., u_{n−1}][/tex] d’entiers. Une sous-suite de u est une suite finie de la forme [tex][u_{i1}, u_{i2}, ..., u_{ip}][/tex] telle que [tex] 0 \leq i_1 < i_2 < ... < i_p \leq n − 1[/tex] et [tex]u_{i1} \leq u_{i2} \leq ... \leq u_{ip}[/tex]

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : [Python]Plus longue sous-suite croissante

re,

ce n'est donc pas ce que j'avais supposé...j'ai eu tort de faire mes propres suppositions sur un énoncé insuffisamment précis !

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : [Python]Plus longue sous-suite croissante

Salut,

Avec la liste u= [2,0,1,5,4,6,7,3], si j'ai bien compris l'énoncé, les listes des sous-suites croissantes sont
[2],[0],[1],[5],[4],[6],[7],[3]
[0,1],[1,5],[4,6],[6,7]
[0,1,5]
avec des indices consécutifs...
Je ne vois donc pas à quelle sous-suite tu te réfères en disant que la longueur max est 5...
Cela dit, puisque tu as écrit :

je connais:
- La longueur de la plus longue sous-suite croissante
- L'indice auquel se termine cette plus longue sous-suite

Tu crées une 3e fonction à qui tu passes en paramètre ta liste u.
Dans cette fonction
tu commences par chercher n = len(u)
Ensuite, comme je ne sais pas comment tu as construit tes fonctions, j'en suis réduit aux généralités.
Tu récupères, en appelant tour à tour les 2 fonctions précédentes, ta LongMax et ton indice_fin...
Pour extraire la sous-suite
- si les indices sont consécutifs, tu demandes u[indice_fin+1-LongMax:Indice_fin+1]
- si les indices ne sont pas consécutifs, tu es préalablement obligée (dans la la recherche de la longueur max) obligée de stocker aussi les indices de tous les éléments d'une sous-suite.
Par ex pour la sous-suite [0,1,4,6,7], la longueur mas m'importe peu si j'ai stocké les indices correspondant :
IndicesListeMax=[1,2,4,5,6]
Dans ce cas :

for i in IndicesListeMax:
    print u[i],

t'affiche :  0 1 4 6 7

@+

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : [Python]Plus longue sous-suite croissante

Bonsoir,

Ainsi avec ces deux fonctions, je connais:
- La longueur de la plus longue sous-suite croissante
- L'indice à laquelle termine cette plus longue sous-suite

Et maintenant j'aimerais connaître à partir de ces informations la dite plus longue sous-suite. J'espère avoir été clair..

Outre ce que pose yoshi, il faudrait dire :

" - La longueur des plus longues sous-suites croissantes, car par exemple :
U : [0,1,7,8,9,2,5,6,3,4] contient 3 sous suites croissantes de longueurs 5 se terminant en 4, 7 et 9 !
Même pour ne redonner que la première des trois, il faut reprendre le tableau u …?!

Il n'est pas dit non plus que le tableau  contient des entiers "tous différents"
Si des entiers peuvent apparaître plusieurs fois, gare aux pièges dans la programmation de tabLongueurMax(u)

miq

Membre

Inscription : 08-01-2014

Messages : 24

Re : [Python]Plus longue sous-suite croissante

Bonjour,

@yoshi: apparemment les éléments des sous-suites ne sont pas nécessairement consécutifs.

Voilà comment j'ai codé la seconde question du problème :

tlm=tabLongueurMax(u)
iCur=iPrev=longueurMax(u)
r=[]
while iPrev>=0:
    r.insert(0,u[iCur])
    iPrev=iCur-1
    while iPrev>=0 and tlm[iPrev]!=tlm[iCur]-1:
        iPrev-=1
    iCur=iPrev
 

avec u=[2, 0, 1, 5, 4, 6, 7, 3]
on obtient tlm=[1, 1, 2, 3, 3, 4, 5, 3]
puis iCur=6
et enfin r=[0, 1, 4, 6, 7]

L'idée est de partir de l'indice de la fin de la sous-liste et de remonter chercher quel est l'indice du précédent le plus proche.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : [Python]Plus longue sous-suite croissante

Salut,

Merci, c'est sympa.
Si les éléments des sous-suites sont consécutifs, ce n'est pas "méchant", d'accord ...
Le problème que j'ai rencontré est le cas : pas forcément consécutifs.
Ça, c'est une autre paire de manches : c'est la première fois, en programmation, que j'ai failli renoncer...

J'ai pourtant écrit, il y a longtemps un logiciel de conjugaison française : je me suis acharner à ce qu'il puisse trouver de lui-même le groupe des verbes, et plus précisément celui des verbes en "ir" qui sont soit du 2e, soit du 3e et ce, sans lexique de verbes.
J'ai fini par trouver une astuce en 4/5 lignes avec quand même une douzaine d'exceptions.

Mais là avec sous-suites, j'ai bien cru devoir capituler...

@+