Discussion :

[hassanJava]

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.

[ToTo13]

Bonjour,

à part une recherche exhaustive, je n'ai pas d'idée...
Ca peut paraître très lourd, mais on peut largement élagué les branches de l'arbre de recherche :
- il faut essayer de commencer avec tous les éléments de la liste (ça c'est lourd), mais dès qu'un chiffre est utilisé dans une liste solution, on sait qu'il ne faut plus démarrer par lui car toutes les listes qu'il engendrerait ne serait pas maximales. Ce qui réduit considérablement les possibilités.

[pseudocode]

on peut aussi construire les listes en partant de la fin.

Le dernier element Z d'une liste maximale est tel qu'il n'y a pas d'element supérieur à Z dans le reste de S.


1. On cherche les elements Z qui peuvent être les derniers elements d'une liste maximale:

Code :

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

1
2
3
 
S = 1,5,6,9,2,3,4,7,8
          ^         ^

=> Les listes maximales de L finissent par Z=9 ou Z=8

2. Split récursif: on a 2 cas à traiter. Les listes qui finissent par 9, et celles qui finissent par 8.

Pour chaque cas, on réduit S aux choix possibles = la liste des éléments de S precedents Z et dont la valeur est inferieure à Z.

cas "Z=9": --> S = 1,5,6
cas "Z=8": --> S = 1,5,6,2,3,4,7

3. retour à l'étape 1, pour chaque Z.


En esperant ne pas avoir dit trop de bétises.

[Graffito]

Bonjour,

Etape 1 : Après avoir inséré en début de liste un nombre égal au minimum absolu (exemple : -2**31), on stoke pour chaque nombre de la liste tous les nombres situés derrière et supérieurs à ce nombre.

Etape 2 : en démarrant du premier élément (le minimum absolu), parcourir toutes les possibiltés de chainages en allant jusqu'au dernier élément sans chainage.

[Jedai]

Une petite implémentation de l'idée de Pseudocode (sauf que moi je part du début, quelle drôle d'idée de vouloir partir de la fin !) :

Code :

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

1
2
3
4
5
6
7
8
9
import Data.List
 
sscm [] = [[]]
sscm xs@(x:_) = concatMap (\(y:ys) -> map (y:) $ sscm $ filter (>=y) ys) cs
    where 
      cs = snd . foldl' isStart (x,[xs]) . init . tails . tail $ xs
      isStart p@(mini,cs) c@(y:_) 
          | y < mini = (y,c:cs)
          | otherwise = p

Et l'idée de Graffito n'est pas tout à fait correcte (à priori sans la phase d'élimination de candidats proposé par Pseudocode, on tombe sur des sous-séquences non maximales).

Une solution en partant de la fin, comme proposé par Pseudocode (avec partage des queues de liste, on pourrait faire pareil en partant du début) :

Code :

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

1
2
3
4
5
6
7
8
9
sscmR [] t = [t]
sscmR rxs@(x:xs) t = concatMap (\(y:ys) -> sscmR (filter (<=y) ys) (y:t)) cs
    where
      cs = snd . foldl' isEnd (x,[rxs]) . init . tails $ xs
      isEnd p@(maxi,cs) c@(y:_) 
          | y > maxi = (y,c:cs)
          | otherwise = p
 
sscm' xs = sscmR (reverse xs) []

--
Jedaï

[pseudocode]

(sauf que moi je part du début, quelle drôle d'idée de vouloir partir de la fin !)

C'est parce que je suis un rebelle.

Et sinon, je suppose que ça marche ? (sinon tu m'aurais lynché)

[hassanJava]

on peut aussi construire les listes en partant de la fin.

Le dernier element Z d'une liste maximale est tel qu'il n'y a pas d'element supérieur à Z dans le reste de S.


1. On cherche les elements Z qui peuvent être les derniers elements d'une liste maximale:

Code :

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

1
2
3
 
S = 1,5,6,9,2,3,4,7,8
          ^         ^

=> Les listes maximales de L finissent par Z=9 ou Z=8

En fait j'ai pas compris comment on peut determiner que les sous-seq maximales d'une seq finissent par quoi? Si j'ai bien compris tu veut dire qu'elle finissent soit par le dernier entier de la seq soit par l'entier le plus grand dans la seq. si c'est le cas, c'est pas tout à fait juste.
Par ex. S={1,5,6,9,2,3,7,8,4}
la, les sous-seq maximales finissent par le 4 ou le 8 ou le 9....

merci d'expliquer.


En plsu j'ai une question peut-etre un êut bête. mais qu'est-ce qu c'est le meilleur implementation d'un arbre n-aire sous java vu la performance surtout quand on parcours l'arbre plusieurs fois.

Merci de tous.

[Jedai]

En fait j'ai pas compris comment on peut determiner que les sous-seq maximales d'une seq finissent par quoi? Si j'ai bien compris tu veut dire qu'elle finissent soit par le dernier entier de la seq soit par l'entier le plus grand dans la seq.

Non c'est pas ce qu'il dit : il dit que les sous-seq maximales ne peuvent se finir que par un nombre plus grand que tous ceux qui le suivent dans la séquence (sinon on pourrait rajouter ce nombre à la sous-séquence croissante, qui ne serait donc pas maximale), ça correspond bien à 4, 8 et 9 dans ton exemple.

Bon alors ma version finale, j'ai pris comme définition d'une séquence croissante une séquence S tel que si i et j sont des indices, i < j => S(i) < S(j). (strictement croissante pourrait-on dire)
Par ailleurs pour l'inclusion, je ne prend en compte que les indices, pas les valeurs, autrement dit je peux renvoyer plusieurs fois la même sous-séquence si elle est présente à plusieurs endroits dans la séquence d'origine.

Ca me donne :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
sscmR :: (Ord a) => [a] -> [a] -> [[a]]
sscmR [] t = [t]
sscmR rxs@(x:xs) t = concatMap (\(y:ys) -> sscmR (filter (<y) ys) (y:t)) cs
    where
      cs = snd . foldl' isEnd (x,[rxs]) . init . tails $ xs
      isEnd p@(maxi,cs) c@(y:_) 
          | y >= maxi = (y,c:cs)
          | otherwise = p
 
sscm :: (Ord a) => [a] -> [[a]]
sscm xs = sscmR (reverse xs) []

La solution de Zavonen a la même sémantique et est infiniment meilleure que sa première proposition mais fait beaucoup trop de vérifications inutiles (par exemple le JustAfter() vérifie trop d'indices, il ne devrait vérifier que ceux dans le After(), de plus il y a pas mal de travail gaché par rapport à mon fold qui transporte le "maximum jusqu'ici"), au final pour S=[1,5,6,9,2,3,4,7,8,10]*14 elle met 37s, là où ma solution met 0,5s.

--
Jedaï

[pseudocode]

merci d'expliquer.

Le dernier élement d'une sous-seq MAXIMALE est tel qu'il n'y a pas d'élement plus grands après lui dans S. Sinon, la sous-seq ne serait pas maximale car on pourrait y ajouter un element au bout.

Donc, pour savoir si un élement de S sera le dernier élement d'une sous-seq maximale, il suffit de regarder s'il y en a d'autres plus grands que lui dans la fin de S.

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

1 --> après il y a 5,6,9,7,8 => pas un dernier element
5 --> après il y a 6,9,7,8 => pas un dernier element
6 --> après il y a 9,7,8 => pas un dernier element
9 --> pas d'element plus grands dans le reste de S => c'est un dernier element
(...)
7 --> après il y a 8 => pas un dernier element
8 --> pas d'element plus grands dans le reste de S => c'est un dernier element
4 --> pas d'element plus grands dans le reste de S => c'est un dernier element

=> les sous-seq maximales finissent par 9, 8 et 4

[hassanJava]

Je vous remercie beaucoup pour les réponses rapides.

En fait comme chercher des sous-seq il fait partie d'un projet de clustering et je l'ai developpé jusqu'à la sous Java, je ne peut donc pas switch sous haskell bien que je le sais pas bien.

alors j'ai mal pour implementer vos idées sous java. En fait comme la performance est l'un des prioritaire dans ce projet alors je ne peut pas le faire avec n'importe quelle structure de code et de données.

Je ne sais pas comment faire pour le meilleur performance sous java surtout comment à la fin récuperer les sous-seq trouvées.

Merci encore.