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é)

[Jedai]

C'est parce que je suis un rebelle.

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

Ca marche très bien, tu as eu l'intuition décisive avec ton histoire de "dernier élément" (ou premier, comme on veut).

Il n'est pas exclu qu'il y ait mieux toutefois.

--
Jedaï

[pseudocode]

c'est parceque j'ai enfin fait le tuto Haskell. Je commence à penser en fonctionnel. Arg! Ca fait 2 réponses de suite que j'ai pensé en fonctionnel !

Heureusement je code encore en Java.

[Graffito]

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).

Exact, il faut effectivement ajouter une contrainte dans l'étape 1 recherche des "suivants", à savoir qu'une fois qu'un suivant a été trouvé, tous les candidats situés derrière ce suivant dans une séquence croissante ne doivent pas être retenus.

[Zavonen]

Ce truc me parait simple à comprendre.
Question perfs je ne sais pas ce que ça vaut.
Je compte sur Jedai pour nous le dire bientôt.

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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# -*- coding: cp1252 -*-
 
S=[1,5,6,9,2,3,4,7,8]
 
# sous suite de S correspondant à une suite binaire 1 on prend 0 on laisse
def sequ(L):
    return [S[i] for i in range(0,len(S)) if L[i]!=0]
 
#teste si deux suites binaires sont incluses l'une dans l'autre
def incluse (L1,L2):
    if L1==[] and L2==[]:
        return True
    if L1[0]>L2[0]:
        return False
    else:
        return incluse (L1[1:],L2[1:])
 
#teste si suite croissante
def croissante (S1):
    if len(S1)<=1:
        return True
    if S1[0]>S1[1]:
        return False
    else:
        return croissante(S1[1:])
 
# retourne les suites  de n éléments de F
def puissance(n,F):
    G=[[x] for x in F]
    for i in range (0,n-1):
        G= [y+[x] for y in G for x in F]
    return G
 
#élimine les éléments non maximaux
def traite (Poss):
    if Poss==[]:
        return Poss
    else:
        Q=Poss[1:]
    for L in Q:
        if incluse(Poss[0],L):
            return traite(Q)
    return [Poss[0]]+traite(Q)
 
#fonction principale
def main():
    R=puissance(len(S),[0,1])
    G=[L for L in R if croissante(sequ(L))]
    print [sequ(L) for L in traite(G)]
 
if __name__ == '__main__':
    main()

[Jedai]

Ce truc me parait simple à comprendre.
Question perfs je ne sais pas ce que ça vaut.
Je compte sur Jedai pour nous le dire bientôt.

Ce truc est simple à comprendre et évidemment extrêmement mauvais... Par acquis de conscience j'ai essayé, mais même sur la séquence de départ x 5 il peine à mort. Bien sûr, j'avais abandonné tout espoir à partir du moment où j'ai vu que tu calculais l'ensemble des listes de 0 ou 1 de la taille de la séquence de départ...
Ta méthode procède par génération et filtrage, mais vu que la génération est purement exponentielle, les performances ne peuvent pas être bonnes. Il faut entremêler génération et filtrage afin d'éliminer des sous-arbres complets de possibilités, sinon l'algo est en O(2^n), ingérable.

Ton programme devient très lent dès 17 éléments dans la séquence et absolument inutilisable un peu après la vingtaine alors que ma fonction sscm' en Haskell reste utilisable avec des centaines d'éléments (200 éléments au hasard dans [-10000,10000], 9_470_532 sous-séquences trouvés, 12s (rien que ton traite() en O(n^2) prendrait des heures pour vérifier ça). Pour les séquences de 140 éléments ou moins, le temps de calcul reste en dessous de la seconde (0.5s de moyenne sur ma machine) ).

Je ne sais pas si on peut faire beaucoup mieux que la proposition de Pseudocode, mais au moins elle apparaît relativement efficace pour une classe de problême de taille raisonnable.

(EDIT : En fait, en supposant que ton incluse prenne une microseconde, le traite() sur 9_470_532 sous-séquences maximales prendrait environ 1 an et demi...)
--
Jedaï

[Zavonen]

Ce truc est simple à comprendre et évidemment extrêmement mauvais...

Je ne suis pas surpris, mon algo est naïf, c'est pourquoi il est simple à comprendre.
En voici un autre, à mon avis encore très lisible et qui à l'air de carburer un peu plus:

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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# -*- coding: cp1252 -*-
 
S=[1,5,6,9,2,3,4,7,8]*5
 
# liste des indices correspondant à des éléments plus grands que l'élément d'indice i
def After(i):
    return [j for j in range(i,len(S)) if S[j]>S[i]]
 
# teste si on ne peut rien intercaler entre les éléments d'indices k et i
def JustAfter(k,i):
    for j in range (k+1,i+1):
        if S[k]<S[j]<S[i]:
            return False
    return True
 
# tous les indices des éléments pouvant suivre l'élément d'indice i dans une suite croissante maximale
def CanFollow(i):
    L=After(i)
    return [k for k in L if JustAfter(i,k)]
 
# teste si l'élément d'indice i peut commencer une suite maximale
def CanBegin(i):
    for j in range (0,i):
        if S[j]<S[i]:
            return False
    return True
 
# Toutes les suites maximales commençant par l'indice i (sous forme d'indices)
def Beg(i):
    L=CanFollow(i)
    if L==[]:
        return [[i]]
    else:
        T=[]
        for j in L:
            T=T+Beg(j)
        return [[i]+ x for x in T]
 
# Toutes les suites maximales sous forme de suites d'indices
def All():
    R=[]
    for i in range(0,len(S)):
        if CanBegin(i):
            R+=Beg(i)
    return R
 
# transforme les indices en éléments de S
def desindexe(L):
    return [S[i] for i in L]
 
# Toutes les solutions
def Solutions():
    return [desindexe(L) for L in All()]
 
 
def main():
    print Solutions()
 
if __name__ == '__main__':
    main()

[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.

[Jedai]

A priori, si tu veux essayer de copier ma solution en Java, il faut que tu utilises des LinkedList. Ce ne sera pas parfait (Linked-List est doublement lié, de plus il faudra que tu fasses des clone() puis addFirst() là où je me contente de faire des cons,etc), mais ce sera assez proche.

Peut-être y aurait-il une façon plus propre de le faire en Java, qui est après tout un langage très différent de Haskell, qu'en pense notre expert Java local Pseudocode ?

--
Jedaï

[pseudocode]

Peut-être y aurait-il une façon plus propre de le faire en Java, qui est après tout un langage très différent de Haskell, qu'en pense notre expert Java local Pseudocode ?

Tiens, j'ai un nouveau titre.

Bon, alors en Java, j'ai la sale habitude de remplir des piles par récursion. Comme ca je gère ma pile (les subseq) et je laisse le compilateur gerer la sienne (les parcours des sous listes)

Code java :

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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
/**
 * @param S La liste de référence
 * @param start Offset de départ dans la liste de référence
 * @param subseq La SubSeq maximale en cours de remplissage 
 * @param subseqlen La taille actuelle de la SubSeq maximale
 */
static void findSubSeq(int[] S, int start, int[] subseq, int subseqlen) {
 
	int min=Integer.MAX_VALUE;
	for(int i=start;i<S.length;i++) {
 
		// ignore les elements qui ne forment pas une subseq strictement croissante
		if (subseqlen>0 && S[i]<=subseq[subseqlen-1]) continue;
 
		// detection d'un element minimal
		if (S[i]<min) {
			min=S[i];
 
			// empilement dans la subseq
			subseq[subseqlen++]=S[i];
 
			// traitement de la liste restante
			findSubSeq(S,i+1,subseq,subseqlen);
 
			// depilement de la subseq
			subseqlen--;
		}
 
	}
 
	// la subseq ne grossit plus -> fini : on affiche
	if (min==Integer.MAX_VALUE) {
		for(int i=0;i<subseqlen;i++)
			System.out.print(subseq[i]+" ");
		System.out.print("\n");
	}
 
}
 
public static void main(String[] args) {
	int[] S = new int[] {1,5,6,9,2,3,4,7,8}; 
 
	long t0 = System.currentTimeMillis();
	findSubSeq(S,0,new int[S.length],0);
	long t1 = System.currentTimeMillis();
 
	System.out.println("duration: "+(t1-t0)+"ms");
}

On peut alléger la récursion en transformant les variables locales de la méthode en variables de classe/instance. Cet exercice est laissé au lecteur.

[Jedai]

Tu as une petite erreur de sémantique (que j'avais également dans ma première version), à cette ligne :

Code :

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

1
2
// detection d'un element minimal
                if (S[i]<min) {

Ceci devrait plutôt être :

Code :

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

1
2
// detection d'un element minimal
                if (S[i]<=min) {

en accord avec ta proposition.
En effet, si tu n'agis pas ainsi, tu manque potentiellement un certain nombre de sscm (j'en ai marre de dire sous-séquence croissante maximale). Du moins du point de vue des indices... Si le posteur initial pouvait nous éclairer sur son besoin ?

En tout cas, je ne sais pas pourquoi exactement, mais ta solution est moins rapide que ma fonction Haskell, mettant dans les 13s pour 140 éléments. En fait, j'ai une idée, c'est parce que tu ne filtres pas comme moi les éléments trop petits pour être inclus dans la sous-séquence en construction, tu retestes tous les éléments de la séquence.

--
Jedaï

[pseudocode]

En effet, si tu n'agis pas ainsi, tu manque potentiellement un certain nombre de sscm (j'en ai marre de dire sous-séquence croissante maximale). Du moins du point de vue des indices... Si le posteur initial pouvait nous éclairer sur son besoin ?

Effectivement, ca dépend si le PO veut des sscm distinctes par "valeur" ou par "indice".

En tout cas, je ne sais pas pourquoi exactement, mais ta solution est moins rapide que ma fonction Haskell, mettant dans les 13s pour 140 éléments.

? Ca serait pas plutot l'affichage des sscm qui ralentit le test ?