Extract Longest Non-Decreasing Sequence From Any Sequence

I wrote some python code that extracts the longest non-decreasing subsequence from any given sequence.

This runs in O(n log n) time, and uses O(n) memory.

''' An item in the final sequence, used to form a linked list. '''
class SeqItem():
    val = 0      # This item's value.
    prev = None  # The value before this one.
    def __init__(self, val, prev):
        self.val = val
        self.prev = prev

''' Extract longest non-decreasing subsequence from sequence seq.'''
def extract_sorted(seq):
    subseqs = [SeqItem(seq[0], None)] # Track decreasing subsequences in seq.
    result_list = [subseqs[0]]
    for i in range(1, len(seq)):
        result = search_insert(subseqs, seq[i], 0, len(subseqs))

    # Build Python list from custom linked list:
    final_list = []
    result = subseqs[-1] # Longest nondecreasing subsequence is found by
                         # traversing the linked list backwards starting from
                         # the final smallest value in the last nonincreasing
                         # subsequence found.
    while(result != None and result.val != None):
        final_list.append(result.val)
        result = result.prev # Walk backwards through longest sequence.

    final_list.reverse()
    return final_list

''' Seq tracks the smallest value of each nonincreasing subsequence constructed.
Find smallest item in seq that is greater than search_val.
If such a value does not exist, append search_val to seq, creating the beginning
of a new nonincreasing subsequence.
If such a value does exist, replace the value in seq at that position, and
search_val will be considered the new candidate for the longest subseq if
a value in the following nonincreasing subsequence is added.
Seq is guaranteed to be in increasing sorted order.
Returns the index of the element in seq that should be added to results. '''
def search_insert(seq, search_val, start, end):
    median = (start + end)/2

    if end - start < 2: # End of the search.
        if seq[start].val > search_val:
            if start > 0:
                new_item = SeqItem(search_val, seq[start - 1])
            else:
                new_item = SeqItem(search_val, None)

            seq[start] = new_item
            return new_item
        else: # seq[start].val <= search_val
            if start + 1 < len(seq):
                new_item = SeqItem(search_val, seq[start])
                seq[start + 1] = new_item
                return new_item
            else:
                new_item = SeqItem(search_val, seq[start])
                seq.append(new_item)
                return new_item

    if search_val < seq[median].val: # Search left side
        return search_insert(seq, search_val, start, median)
    else: #search_val >= seq[median].val: # Search right side
        return search_insert(seq, search_val, median, end)

And here is an example usage:

import random
if __name__ == '__main__':
    seq = []
    for i in range(100000):
        seq.append(int(random.random() * 1000))

    print extract_sorted(seq)
This entry was posted in Coding, Misc and tagged , . Bookmark the permalink.

10 Responses to Extract Longest Non-Decreasing Sequence From Any Sequence

  1. Mac says:

    Yo, this shit doesn’t fucking work

  2. olhovsky says:

    Can you be a little bit more specific?
    E.g., tell me a sequence that this algorithm doesn’t work on.

    I have verified this against a few million random strings which were solved using a more brute force approach, so I’d be surprised if there is an error.

  3. newur says:

    Hey,

    that was (nearly) excact what i was looking for. Had to write this for univerisity in Java. In the end my resulting code looks MUCH different and is not as fast as yours, but its still okay. Without your example I would have never find a solution (and it took only 3 Hours of try-and-error to understand, how it works ^^)

    Thanks for sharing, man. :)

  4. olhovsky says:

    Hey someone found a use for this?! Well, that’s more than I expected when posting it :)

  5. brian says:

    Nice to know it’s here if I ever need it. I like the format of the listing too (fixed pitch, alternating shading).

  6. Pingback: Problem Solving: Growing Sequences « My Trip Through CSC165

  7. Thanh says:

    This problem with your algorithm is not applicable.
    Write an algorithm which reads a sequence of real numbers and determines the length of the longest non-decreasing subse-
    quence. For instance, in the sequence
    7,8,7,8,9,2,1,8,7,9,9,10,10,9,
    the longest non-decreasing subsequence is 7,9,9,10,10, of length 5.

  8. olhovsky says:

    @Thanh: It’s trivial to modify the algorithm I gave to produce the longest non-decreasing subsequence, instead of the longest increasing subsequence. In fact, I think it’s just a matter of changing/adding a few characters. What application do you have in mind by the way? I had no application in mind when solving this problem — a professor of mine claimed to have an O(n^2) solution, so I produced an O(n log n) algorithm in response.

  9. testdomain says:

    Thanks a whole lot for this great post on adjustable piano bench. I will keep it mind when I am searching for a piano seat..

  10. I have to express appreciation to you just for bailing me out of this particular instance. As a result of looking throughout the the net and obtaining notions which are not powerful, I believed my entire life was well over. Existing without the presence of solutions to the issues you have fixed by means of your entire review is a serious case, as well as the ones which might have negatively affected my career if I hadn’t come across your website. Your personal training and kindness in handling every aspect was tremendous. I’m not sure what I would have done if I hadn’t encountered such a step like this. I’m able to at this time look forward to my future. Thanks for your time so much for this skilled and results-oriented help. I won’t be reluctant to suggest your web page to anybody who desires counselling about this issue.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>