Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I have a list, for example

list = {2, 1, 3, 5, 4, 6}

How to find longest ascending sequence of this list?

There are two meanings of this question:

  1. Find the largest subset that $$ X_{i_1} < X_{i_2} < \ldots < X_{i_{n-1}} < X_{i_n} $$ where $$ i_1 < i_2 < \ldots < i_{n-1} < i_n $$

  2. Find the largest subsequence that

    $$ X_i < X_{i+1} < \ldots < X_{j-1} < X_{j} $$

share|improve this question
add comment

1 Answer 1

up vote 13 down vote accepted
  1. There is an undocumented function LongestAscendingSequence

    LongestAscendingSequence[list]
    
    {1, 3, 4, 6}
    

    This was mentioned here and here in comments. I hope it will not be treated as a duplicate. I think Q&A-style on SE is more appropriate for this question.

  2. For completeness I ask the second question. It seem to be much simpler but I can't find any simple function. My own answer:

    longest1[list_] := #[[Position[#, Max[#]][[1, 1]] &[Length /@ #]]] &@ Split[list, Less];
    longest2[list_] := list[[#2 - # ;; #2 &[Max[#], Position[#, Max[#]][[1, 1]]] &@
        FoldList[(#1 + #2) #2 &, 0, UnitStep@Differences[list]]]];
    
    longest1[list]
    longest2[list]
    
    {1, 3, 5}
    {1, 3, 5}
    

    longest2 is faster for big lists:

    RandomSeed[0];
    list = RandomReal[NormalDistribution[], 1000000];
    
    longest1[list] // AbsoluteTiming
    longest2[list] // AbsoluteTiming
    
    {0.925531, {-2.15449, -1.60199, -0.903194, -0.678062, -0.294706, 
       -0.270457, 0.219321, 0.677958, 1.07586}}
    {0.228277, {-2.15449, -1.60199, -0.903194, -0.678062, -0.294706, 
       -0.270457, 0.219321, 0.677958, 1.07586}}
    
share|improve this answer
    
I doubt this is "undocumented" in the real sense of the word... it's more likely that it was an oversight in writing the documentation for it. Nevertheless, this is not a duplicate, so thanks for asking&answering to document it! :) –  rm -rf Oct 18 '13 at 17:26
1  
+1. The shortest way previously known to me using built-ins is LongestCommonSequence[list, Sort@list], but LongestAscendingSequence is quite a bit faster. I may add another answer later which uses Compile, if I see that it is competitive with LongestAscendingSequence . –  Leonid Shifrin Oct 18 '13 at 18:46
2  
For the second one I'd use MaxBy[Split[list, Less], Length], utilizing MaxBy, which is part of my "mental toolbox". (Note that MaxBy will only return a single result even if there are several equivalent maximal elements.) –  Szabolcs Dec 6 '13 at 14:54
    
@LeonidShifrin did you find that the compiled approach was uncompetitive, or did you just not have time to try it? This was my first thought as well, and it would be interesting to know whether LongestAscendingSequence is really as fast as it can be, or whether one can do better. –  Oleksandr R. Dec 7 '13 at 21:09
    
@OleksandrR. I just did not have the time. I don't have a C compiler installed on a machine I work with currently most of the time, and the last few months were very busy. Later, I forgot about it. If I don't forget this time, I will test this, and report my findings here - but I can't promise when this happens :) –  Leonid Shifrin Dec 7 '13 at 22:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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