Finding All possible Longest Increasing subsequence

Question

I want to find all possible Longest Increasing Subsequences in a given string.

For eg: Given string is qapbso

Here the length of longest increasing subsequence is 3. I want to find all possible longest subsequence of length 3. i.e "abs", "aps", "abo".

I am using Dynamic Programming but I am only getting one LIS. I want to list down all of them.

if you are specifying a required subsequence length, do you still need to include the notion of 'longest possible'? — The Nail
No, I am not specifying the subsequnce length. Here the length of longest LIS is 3, I have just mentioned it for clarity. — dejavu
[Sorry I just removed a relevant comment]. You could disable one edge in the graph (see Benoit's answer) at a time, and leave the rest enabled. But yes, it would be one of the most inefficient algorithms of all times... — The Nail

Ivaylo Strandjev Ivaylo Strandjev · Accepted Answer · 2012-03-04T11:04:39

So the typical DP solution to this will produce an array in which you know what is the longest possible subsequence starting at a given position i let's say that you have and array with length n in which dp[i] stores the length of the longest non-decreasing subseq that starts with the element with index i.

Now printing all the LNDSS(longest non-decreasing subsequences) is easiest to be done using a recursion. First find the actual length of the LNDSS by seleting the greast value in dp. Next start the recursion from each element in dp that has the maximum value in dp(these may be more then one). The recursion from a given index should print all the sequences starting from the current index that have length equal to the value dp[i]:

int st[1000];
int st_index
void rec(int index) {
  if (dp[index] == 1) {
    cout << "Another sequence:\n";
    for (int i = 0; i < st_index; ++i) {
      cout << st[i] << endl;
    }
  }
  for (int j = index + 1; j < n; ++j) {
    if (dp[j] == dp[index] - 1 && a[j] >= a[index]) {
      st[st_index++] = a[j];
      rec(j);
      st_index--;
    }
  }
}

This is example code in c++(hope it is understandable in other languages as well). I have a global stack called stack that keeps the elements we have already added. It has size 1000 assuming you will never have more then 1000 elements in the LNDSS but this can be increased. The solution does not have the best possible design, but I have focused on making it simple rather then well designed.

Hope this helps.

Finding All possible Longest Increasing subsequence

3 Answers