all maximal increasing subsequences

[hassanJava]

Hi there,
I'm developing a program that for a part of it I need to find all maximal increasing subsequences of a sequence of integer.
I try to clarify the problem :

Given sequence of Integer S={1,5,6,9,2,3,4,7,8}
I want to find all maximal increasing subsequence of S.

a maximal increasing subsequence is a subsequence that its items are ordered increasingly and it's not a subsequence of other subsequences (maximal). It can have any size.

for example : S1={1,5,6,9} or S2={1,5,6,7,8} are maximal increasing subsequence of S as the items are increasing and one can not find any other subsequence who is super sequence of them. BUT S3={1,5,6,2} is not increasing or S4={6,7,8} is not maximal as there is a subsequence like S5={1,5,6,7,8}.

There is alot of works to find "LIS" (longest increasing subsequence) even some that work with O(n log n) complexity but they give just longest increasing sequence but not all increasing subsequences from any size.

I have an algo to do that but it's O(n²) but I like to find one with higher performance.

I should notice that it's possible to have few increasing subsequences who have the same size but are different.

I will be so thankful if you give an algo complete it with a pesudo code to better inspire the used data structure.

Many thanks.

[Chris.Brown.SPE]

Have you tried using recursive backtracking with a global results table? Also, what is your minimum size of a subsequence? 1,2,3 elements?

[hassanJava]

Quote:

Have you tried using recursive backtracking with a global results table? Also, what is your minimum size of a subsequence? 1,2,3 elements?

Hi
I did not understand what you mean by global results table. but I dont see any benefit from backtracking. I mean what's different for ex it's possible that all higher numbers were at first of seq.

anyway, there is not any limit on minimum sous-seq size. il cab be simply one item.

Thanks for reply.

[Chris.Brown.SPE]

The only other idea i have is a spin off of brute forcing it. Go through the string counting every time it goes up, but then save the location it decreases so you know where to start from next time. See the example below:

Data: 3,5,8,10,4,7,12,2,17

When it hits the 4, it saves the location and continues.

I would have a temp variable to hold it and have its default value set as -1 so if it finishes with a -1 it knows it's finished and if there is a decrease and it's not -1 then it wont overwrite it.

Then the next time through the loop it starts at the location of the 4 since it is pointless to check the 5,8, or 10. Then continue the cycle comparing the length of the subsequences each time to store the greatest one. This will get you the longest increasing subsequence.

To get all of them, just do the same thing but store each iteration through the loop.

I hope this makes a little sense.