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

Question

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.

cs_piotrr · Answer

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

cs_hassanJava · Answer

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

cs_jojolemariole · Answer

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

cs_hassanJava · Answer

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+

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

4 réponses

Votre réponse

Discussions similaires