snippetMinor
How to output all longest decreasing sequences
Viewed 0 times
decreasingalloutputhowlongestsequences
Problem
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.
Pseudocode will be helpful.
Solution
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.
$$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.
Context
StackExchange Computer Science Q#1290, answer score: 4
Revisions (0)
No revisions yet.