Toutes les sous-sequences croissantes et maximales d'une séquence des entiers

Signaler
Messages postés
3
Date d'inscription
lundi 21 avril 2008
Statut
Membre
Dernière intervention
22 avril 2008
-
Messages postés
3
Date d'inscription
lundi 21 avril 2008
Statut
Membre
Dernière intervention
22 avril 2008
-
Bonjour,

Je suis en trains de développer une application et pour une partie de
ca j'ai besoin de trouver toutes les sous-séquences croissantes d'une
séquence des entiers qui sont aux-même maximales .


Je m'explique:


Imaginons la séquences des entiers S={1,5,6,9,2,3,4,7,8}

une sous-séquence croissantes est une sous-séquences de S dont les
items sont dans l'ordre croissantes. Une sous-séquence est maximale si
elle n'est pas la sous-séquence des autres sous-séquences.


Par ex :

S1={1,5,6,9} ou S2={1,5,6,7,8} sont sous-sequences croissantes et
maximales de S. Mais S3={1,5,6,2} n'est pas croissante ou la
sous-sequence S4={6,7,8} n'est pas maximale comme il y a une autre
sous-sequence S5={1,5,6,7,8} qui contiens S4.


Alors le problématique est de chercher toutes les sous-séquences croissantes et maximales de S.


A dire qu'il y a pleins de travailles sur "LIS" (Longest Increasing
Subsequence) (la sous-sequence croissante la plus longue) même des
algos avec complexité O(n log n) mais j'ai pas trouvé une solution qui
rend toutes les sous-sequences croissantes et maximales de n'importe
quelle tille.


Par exemple sur seq S, j'aimrais de trouver les sous-séquences croissantes et maximales ci-dessous :

{1,5,6,9} {1,5,6,7,8} {1,2,3,4,7,8}

je remarque que c'est possible d'avoir plusieurs sous-sequences
croissantes maximales exactement de la même taille. donc on
s'intéresser d'avoir toutes pas juste une parmi toutes.


Je vous remercie bien de fournir un pesudo code si vous donner un algo
pour mieux faire inspirer le structure de données utilisé.


En vous remerciant j'attends vos réponses.

4 réponses

Messages postés
9
Date d'inscription
jeudi 12 juillet 2007
Statut
Membre
Dernière intervention
21 avril 2008

Tu prends un papier.
Tu prends un crayon.
T'écris l'algo.

signé A.G
Messages postés
3
Date d'inscription
lundi 21 avril 2008
Statut
Membre
Dernière intervention
22 avril 2008

Merci d'avoir pris du temps pour repondre.
Mais eviter de moquer, si tu cherche une peu sur google tu vois que c'est problem pas forcement facil à résoudre dans un complexité polynomiale.

Alors si tu sais pas tu n'est pas obligé d'écrir. En plus comme j'ai dit j'ai fait une algo qui le fait dans O(n²) mais je cherche un algo polynomiale pour la raison de performance.

Merci
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
25
Ce que cherche à dire piotrr, je pense, est que ton problème a tout d'un "exercice d'algorithmique". Si tu pouvais nous expliquer un peu pourquoi ton application a besoin d'un tel algorithme ce serait un plus.

J'ai quelques remarques qui pourront quand même t'aider. D'abord O(n²) est une complexité polynomiale, c'est moins bien que O(n log n) mais c'est déjà pas si mal. Ensuite, je te suggère d'essayer la méthode dichotomique. Même si je n'ai jamais essayé de résoudre ce problème ça sent le bon plan pour la dichotomie.

http://fr.wikipedia.org/wiki/Dichotomie
Messages postés
3
Date d'inscription
lundi 21 avril 2008
Statut
Membre
Dernière intervention
22 avril 2008

Bonjour,
Alors je suis en trains de faire une application de clustering d'un sort particulier des séquence nomme motifs séquentiels dans le domaine fouille de donées.. pour trouver la similarité entre de séquence j'ai besoin d'avoir toutes les sous-séquences de deux séquences.

En plsu si vous regardez sur l'internet vous voyez que c'est un sujet de recherche normalement et donc pas un execrice de cours.

Je sais que O(n²) n'est pas si mal mais si on consider le cas où on a plus de 10 000 séquence à clustering donc la performance sera l'un des prioritaire.

Je vais regarde l'algo Dichotomie et si je trouve un solution en l'utilisant je vous tiens au courant.

Merci beaucoup pour la réponse.
A+