How to output all longest decreasing sequences - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-11-21T14:16:31Z https://cs.stackexchange.com/feeds/question/1290 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/1290 4 How to output all longest decreasing sequences Jack https://cs.stackexchange.com/users/1001 2012-04-15T12:49:34Z 2012-10-11T21:22:02Z <p>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.</p> <p>Pseudocode will be helpful.</p> https://cs.stackexchange.com/questions/1290/-/1291#1291 -3 Answer by Chaithanya for How to output all longest decreasing sequences Chaithanya https://cs.stackexchange.com/users/423 2012-04-15T14:13:11Z 2012-04-15T15:23:42Z <p>For every decreasing sequence, store the initial positions in another array.</p> <pre><code>for( i = 0; i &lt; n-1; i++ ) { if ( a[i] &gt; a[i+1] ) { temp[j++] = i; while( a[i] &gt; a[i+1] ) { i++; } temp[j++] = i; } } </code></pre> <p>Now the array temp will contain initial and final positions of all the decreasing sequences consecutively. Then print them </p> https://cs.stackexchange.com/questions/1290/-/1313#1313 4 Answer by user742 for How to output all longest decreasing sequences user742 https://cs.stackexchange.com/users/0 2012-04-16T21:39:04Z 2012-05-12T11:53:47Z <p>Consider the following sequence as your input:</p> <p>$$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, ....$$</p> <p>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$.</p> <p>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$ &rarr; $b$, if $a &gt; b$ and $b$ is after $a$ in original sequence.</p> <p>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.</p> https://cs.stackexchange.com/questions/1290/-/1410#1410 1 Answer by Sim for How to output all longest decreasing sequences Sim https://cs.stackexchange.com/users/78 2012-04-21T11:27:14Z 2012-04-21T19:43:38Z <p>-a recursive helper function</p> <pre><code> 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 &gt; array[i] list sbuffer sbuffer = form_longest_sublist_from(array,buffer,i); if length sbuffer &gt; length ret ret = sbuffer; endif endif endfor return ret; endfunc </code></pre> <ul> <li><p>The algorithm to use the function</p> <pre><code>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] &lt; last buffer list sbuffer; sbuffer = form_longest_sublist_from(array,buffer,x); if length sbuffer &gt; length buffer) buffer = sbuffer; endif endif endfor if length arrayoflongestlist &gt; 0 if length (last arrayoflongestlist) &lt; 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) &gt; i) break; else add buffer to arrayoflongestlist endif endfor </code></pre></li> </ul> <p>I basically redid the whole algorithm to be a fit for the problem.</p> <p>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.</p> <p>My possible worst/bestcase scenarios mentioned before are of cause not correct considering this algorithm. </p>