4
$\begingroup$

Suppose I have an array of integers having length $N$. How can I output all longest decreasing sequences? (A subsequence consists of elements of the array that do not have to be consecustive, for example $(3,2,1)$ is a decreasing subsequence of $(7,3,5,2,0,1)$.) I know how to calculate the length of longest decreasing sequences, but don't know how to report all longest decreasing sequences.

Pseudocode will be helpful.

$\endgroup$
  • $\begingroup$ A dumb solution would be to build the induced DAG and traverse all paths from source to sink. $\endgroup$ – Suresh Apr 16 '12 at 0:17
  • $\begingroup$ As you know the length of longest decreasing sequence how about DLS on the induced DAG? $\endgroup$ – Pratik Deoghare Apr 17 '12 at 14:49
4
$\begingroup$

Consider the following sequence as your input:

$$n,n-2,n-1,n-3,n-5,n-4,n-6,n-8,n-7,n-9, .... , n-3 \cdot k - 2, n-3 \cdot k - 1, n-3 \cdot k - 3, ....$$

for simplicity assume $n = 3\cdot t + 1$, longest decreasing subsequence length will be $t$ and number of decreasing subsequence of length $t$ is $2^t$.

So number of avilable solutions is $\Theta(2^{n/3})$. But why is so, simply model it with DAG, take care there is an edge from $a$ → $b$, if $a > b$ and $b$ is after $a$ in original sequence.

So because output size can be exponential, your best choice is creating DAG, and finding all longest paths in DAG or any other ways which enumerates all acceptable ways.

$\endgroup$
  • 1
    $\begingroup$ That is not what "EXPTIME-complete" means. $\endgroup$ – JeffE Apr 17 '12 at 5:06
  • $\begingroup$ @JeffE, I don't know,but what should I say when the number of output is exponential? $\endgroup$ – user742 Apr 17 '12 at 7:04
  • 3
    $\begingroup$ You should say "The output size could be exponential." $\endgroup$ – JeffE Apr 17 '12 at 7:16
1
$\begingroup$

-a recursive helper function

    list form_longest_sublist_from(list array,list buffer,from) 
            add array[from] to buffer

            list ret as copy of buffer
            from i = from - 1 to -1 step -1
                   if last buffer > array[i] 
                   list sbuffer
                   sbuffer = form_longest_sublist_from(array,buffer,i);
                   if length sbuffer > length ret
                      ret = sbuffer;
                   endif
                endif
            endfor
            return ret;
    endfunc
  • The algorithm to use the function

    list of lists arrayoflongestlist
        list buffer;
        from i = length array - 1 to -1 step -1
            clear buffer
            add array[i] to buffer
            from x = i - 1 to -1 step -1
                if(array[x] < last buffer
                    list sbuffer;
                    sbuffer = form_longest_sublist_from(array,buffer,x);
                    if length sbuffer > length buffer)
                        buffer = sbuffer;
                                endif
                endif
            endfor
                if length arrayoflongestlist > 0
                       if length (last arrayoflongestlist) < length buffer
                                clear arrayoflongestlist
                                add buffer to arrayoflongestlist
                       endif
                       else if length (last arrayoflongestlist) == length buffer
                    add buffer to arrayoflongestlist
                endif
    
                       if length (last arrayoflongestlist) > i)
                    break;
            else
                add buffer to arrayoflongestlist
            endif
        endfor
    

I basically redid the whole algorithm to be a fit for the problem.

The basic idea is to start from each possible point (each element) in the array and form all possible decreasing sublists by going thorugh the rest of the array and see which elements are smaller and use those elements to start a recursion which does the same mentioned before starting from that point and then filtering the recursions for the longest list given back.

My possible worst/bestcase scenarios mentioned before are of cause not correct considering this algorithm.

$\endgroup$
  • $\begingroup$ How worth case is $O(n^2)$? did you read my answer? output size could be exponential. $\endgroup$ – user742 Apr 21 '12 at 14:40
  • $\begingroup$ might have a flaw in my logic but doesn't my algorithm do (n) + (n-1) + (n-2) + ... + (n- (n-1)) steps in worst case, and therefore you got n(n-1)/2 as a result which basically is O(n²). $\endgroup$ – Sim Apr 21 '12 at 18:22
  • $\begingroup$ Would you describe your algorithm, just add comments and say your general idea. $\endgroup$ – user742 Apr 21 '12 at 18:51
  • $\begingroup$ I just realized a flaw in my answer, as there might be a longer consecutive list, if you might skip the next smaller one $\endgroup$ – Sim Apr 21 '12 at 19:05
  • $\begingroup$ i redid the algorithm and now it does fit the actual problem and does give correct results as far as i was able to test it $\endgroup$ – Sim Apr 21 '12 at 19:44
-3
$\begingroup$

For every decreasing sequence, store the initial positions in another array.

for( i = 0; i < n-1; i++ ) {
    if ( a[i] > a[i+1] ) {
        temp[j++] = i;
        while( a[i] > a[i+1] ) {
            i++;
        }
        temp[j++] = i;
    }
}

Now the array temp will contain initial and final positions of all the decreasing sequences consecutively. Then print them

$\endgroup$
  • 3
    $\begingroup$ This funds only contiguous subsequences, otherwise known as substrings. [4,3,2,1] is a longest decreasing subsequence of [4,6,3,7,8,10,2,11,17,1,99]. $\endgroup$ – JeffE Apr 15 '12 at 22:09
  • $\begingroup$ Can you be clear. For the sequence you provided, the values of temp[] will be 5,6,8,9 i.e., positions of 10,2,17,1. As I mentioned, consecutive values will show the position of sequences. 5,6 and 8,9 are two decreasing sequences $\endgroup$ – Chaithanya Apr 16 '12 at 4:59
  • 2
    $\begingroup$ I think that JeffE is clear; your algorithm fails to produce the correct answer [4, 3, 2, 1] (at indices 0, 2, 6, 9) in JeffE’s example. $\endgroup$ – Tsuyoshi Ito Apr 16 '12 at 8:55
  • $\begingroup$ Sorry, I thought that the sequences are to be consecutive. Now I understand the problem $\endgroup$ – Chaithanya Apr 16 '12 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.