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.

[dinobogan]

Tout d'abord, il te faut décider de la structure de données qui va accueillir les résultats.
Je te propose un arbre n-aire dont chaque noeud possède un lien vers sont père. Chaque noeud aura deux attributs : une valeur du tableau et l'indice de sa position dans le tableau. La racine de l'arbre aura pour valeur Integer.MIN_VALUE, et pour indice -1. On peut imaginer qu'une méthode récursive va remplir l'arbre.
Juste avant le premier appel, ajoute un noeud à la racine avec la première valeur du tableau.
Voici le pseudo-code d'initialisation et de remplissage :

Code :

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

1
2
3
4
5
racine = new instance
racine.value = Integer.MIN_VALUE
racine.index = -1
noeud = racine.add( tab[ 0 ], 0 )
recursive( noeud, tab, 1, Integer.MAX_VALUE )

Voici la méthode récusrive :

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
recursive( noeud, tab, int current, int max )
{
  boolean trouve = false
  tant que current < tab.length & tab[ current ] < max & noeud.value < tab[ current ]
    noeud = noeud.add( tab[ current ], current )
    trouve = true
    max = Integer.MAX_VALUE
  fin tant que
 
  si trouve
    chercher un noeud parent dont la difference de valeur avec son fils est >= 2
    si parent existe
      recursive( parent, tab, parent.index + 1, fils.value )
    fin si
  fin si
}

Maintenant, il te suffit de faire un parcours en profondeur de l'arbre n-aire et tu as toutes tes sous-séquences maximale.

[hassanJava]

Bonjour et merci pour la réponse
En fait la il y a un petit souci. Je m'explique :
Si dans la séquence originale le premier entier n'est le plus petit alors ca donne pas toutes les sous-séquence, par exemple dans la séquence :{3,2,5,6,1,4}
on commence par 3, alors on cherche un entier plus que 3 et on arrive à 5 et on ajoute un neoud et ainsi de suite. mais on ne selectionne alors pas le 2 comme le debut d'une autre sous-séquence, de même pour le 1. Bref, on trouve les sous-séquence 3,4 et 3,5,6 mais pas les sous-séquence commancant par 2 ou 1 comme 2,5,6 ou 1,4

Alors dans la fontion recursive il faut ajouter un truc :

Si !(noeud.value < tab[ current ]) alors ajouter au racine un neoud avec current item.

Dans ce cas la ca marche bien, mais je me demande de la performance de ce méthode, il y a un parcours de la séquence originale en plus après chaque parcours il faut faire une comparaison 2 à 2 sur les fils pour chercher les différences. En plus il faut tout repeter pour le nouvelle neoud ajoutès au racine. il me semble pas que ca cout moins chère que o(n²)