Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I just stumbled in this problem, and came up with this Python 3 implementation:</p> <pre class="lang-py prettyprint-override"><code>def subsequence(seq): if not seq: return seq M = [None] * len(seq) # offset by 1 (j -&gt; j-1) P = [None] * len(seq) # Since we have at least one element in our list, we can start by # knowing that the there's at least an increasing subsequence of length one: # the first element. L = 1 M[0] = 0 # Looping over the sequence starting from the second element for i in range(1, len(seq)): # Binary search: we want the largest j &lt;= L # such that seq[M[j]] &lt; seq[i] (default j = 0), # hence we want the lower bound at the end of the search process. lower = 0 upper = L # Since the binary search will not look at the upper bound value, # we'll have to check that manually if seq[M[upper-1]] &lt; seq[i]: j = upper else: # actual binary search loop while upper - lower &gt; 1: mid = (upper + lower) // 2 if seq[M[mid-1]] &lt; seq[i]: lower = mid else: upper = mid j = lower # this will also set the default value to 0 P[i] = M[j-1] if j == L or seq[i] &lt; seq[M[j]]: M[j] = i L = max(L, j+1) # Building the result: [seq[M[L-1]], seq[P[M[L-1]]], seq[P[P[M[L-1]]]], ...] result = [] pos = M[L-1] for _ in range(L): result.append(seq[pos]) pos = P[pos] return result[::-1] # reversing </code></pre> <p>Since it took me some time to understand how the algorithm works I was a little verbose with comments, and I'll also add a quick explanation:</p> <ul> <li><code>seq</code> is the input sequence.</li> <li><code>L</code> is a number: it gets updated while looping over the sequence and it marks the length of longest incresing subsequence found up to that moment.</li> <li><code>M</code> is a list. <code>M[j-1]</code> will point to an index of <code>seq</code> that holds the smallest value that could be used (at the end) to build an increasing subsequence of length <code>j</code>.</li> <li><code>P</code> is a list. <code>P[i]</code> will point to <code>M[j]</code>, where <code>i</code> is the index of <code>seq</code>. In a few words, it tells which is the previous element of the subsequence. <code>P</code> is used to build the result at the end.</li> </ul> <p>How the algorithm works:</p> <ol> <li>Handle the special case of an empty sequence.</li> <li>Start with a subsequence of 1 element.</li> <li>Loop over the input sequence with index <code>i</code>.</li> <li>With a binary search find the <code>j</code> that let <code>seq[M[j]</code> be <code>&lt;</code> than <code>seq[i]</code>.</li> <li>Update <code>P</code>, <code>M</code> and <code>L</code>.</li> <li>Traceback the result and return it reversed.</li> </ol> <p><strong>Note:</strong> The only differences with the <a href="http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms" rel="noreferrer">wikipedia algorithm</a> are the offset of 1 in the <code>M</code> list, and that <code>X</code> is here called <code>seq</code>. I also test it with a slightly improved unit test version of the one showed in <a href="https://stackoverflow.com/a/7918909/1132524">Eric Gustavson answer</a> and it passed all tests.</p> <hr> <p>Example:</p> <pre class="lang-py prettyprint-override"><code>seq = [30, 10, 20, 50, 40, 80, 60] 0 1 2 3 4 5 6 &lt;-- indexes </code></pre> <p>At the end we'll have:</p> <pre class="lang-py prettyprint-override"><code>M = [1, 2, 4, 6, None, None, None] P = [None, None, 1, 2, 2, 4, 4] result = [10, 20, 40, 60] </code></pre> <p>As you'll see <code>P</code> is pretty straightforward. We have to look at it from the end, so it tells that before <code>60</code> there's <code>40,</code>before <code>80</code> there's <code>40</code>, before <code>40</code> there's <code>20</code>, before <code>50</code> there's <code>20</code> and before <code>20</code> there's <code>10</code>, stop.</p> <p>The complicated part is on <code>M</code>. At the beginning <code>M</code> was <code>[0, None, None, ...]</code> since the last element of the subsequence of length 1 (hence position 0 in <code>M</code>) was at the index 0: <code>30</code>. </p> <p>At this point we'll start looping on <code>seq</code> and look at <code>10</code>, since <code>10</code> is <code>&lt;</code> than <code>30</code>, <code>M</code> will be updated:</p> <pre class="lang-py prettyprint-override"><code>if j == L or seq[i] &lt; seq[M[j]]: M[j] = i </code></pre> <p>So now <code>M</code> looks like: <code>[1, None, None, ...]</code>. This is a good thing, because <code>10</code> have more chanches to create a longer increasing subsequence. (The new 1 is the index of 10)</p> <p>Now it's the turn of <code>20</code>. With <code>10</code> and <code>20</code> we have subsequence of length 2 (index 1 in <code>M</code>), so <code>M</code> will be: <code>[1, 2, None, ...]</code>. (The new 2 is the index of 20)</p> <p>Now it's the turn of <code>50</code>. <code>50</code> will not be part of any subsequence so nothing changes.</p> <p>Now it's the turn of <code>40</code>. With <code>10</code>, <code>20</code> and <code>40</code> we have a sub of length 3 (index 2 in <code>M</code>, so <code>M</code> will be: <code>[1, 2, 4, None, ...]</code> . (The new 4 is the index of 40)</p> <p>And so on...</p> <p>For a complete walk through the code you can copy and paste it <a href="http://netserv.ict.ru.ac.za/python3_viz/" rel="noreferrer">here</a> :)</p>
    singulars
    1. This table or related slice is empty.
    1. POLongest increasing subsequence
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USRik Poggi
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POLongest increasing subsequence
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COAh! Python is so much better, and your comments help. I'll look at it in more detail in the morning.
      singulars
      1. PO
      1. USJungle Hunter
    2. COI added an example, I hope the post is not too long now...
      singulars
      1. PO
      1. USRik Poggi
    3. COLong is good. Thanks so much!
      singulars
      1. PO
      1. USJungle Hunter
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload