How do I split a list of numbers to monotonic sequences?

Question

Suppose I have:

list = {1, 2, 4, 5, 7, 11, 8, 7, 3, 1, -3, -2, 6, 7, 80}

And I want to split it to:

{{1, 2, 4, 5, 7, 11}, {8, 7, 3, 1, -3}, {-2, 6, 7, 80}}

What should I do?

Split[#, Less]& or Split[#, Greater]& seems to only do half of the job.

And the Split condition seems only accept two arguments(#1, #2 but no #3).

Answer 1

Starting at 10.1, there's a fairly neat solution using SequenceCases:

list = {1, 2, 4, 5, 7, 11, 8, 7, 3, 1, -3, -2, 6, 7, 80};
SequenceCases[list, x_ /; Less @@ x || Greater @@ x]
(* {{1, 2, 4, 5, 7, 11}, {8, 7, 3, 1, -3}, {-2, 6, 7, 80}} *)

This works because SequenceCases defaults to Overlaps -> False, such that e.g. 11 won't appear in two of the sublists.

Of course, if you want to allow repeated elements (i.e. not strictly monotonic sequences), use LessEqual and GreaterEqual respectively.

For a pre-10.1 solution using Split see Xavier's answer.

Answer 2

Martin provided a nice answer with SequenceCases. For Mathematica versions prior to 10.1, depending on what OP wants for lists of the form:

list2 = {1, 2, 4, 5, 7, 11, 8, 9, 10, 12, -3, -2, 6, 7, 80};

namely, for lists that have consecutive sequences of same monotonicity, an approach could be:

splitMon[list_] := 
    Split[list, 
        sign =.; 
        If[sign (#2 - #1) > 0, True, sign =.; False, sign = Sign[#2 - #1]; True] &
    ];

Examples:

SequenceCases[list, x_ /; Less @@ x || Greater @@ x]
% === splitMon[list]

(* {{1, 2, 4, 5, 7, 11}, {8, 7, 3, 1, -3}, {-2, 6, 7, 80}} *)
(* True *)

SequenceCases[list2, x_ /; Less @@ x || Greater @@ x]
% === splitMon[list2]

(* {{1, 2, 4, 5, 7, 11}, {8, 9, 10, 12}, {-3, -2, 6, 7, 80}} *)
(* True *)

Answer 3

Here's a solution using SplitBy. It works also for elements that are repeated no more than once, but it can be fixed if there are elements repeated more than once.

monotonicSplit[list_] := SplitBy[Transpose[{#, {#1, ##} & @@ Sign@Differences@#}] &@list, Last][[All, All, 1]]

list = {1, 2, 4, 5, 6, 6, 7, 3, 1, -3, -2, 6, 7, 80};
monotonicSplit[list]
(* {{1, 2, 4, 5, 6}, {6}, {7}, {3, 1, -3}, {-2, 6, 7, 80}} *)

Answer 4

Here's a recursive way:

ClearAll[monoSplit];
monoSplit[{pre___, a_, b_, c_, post___}] /; (a < b && b > c) || (a > b && b < c) :=Sequence[{pre, a, b}, monoSplit[{c, post}]];
monoSplit[{pre___, a_, b_, c_, post___}] := {pre, a, b, c,  post};
monoSplit[{a_}] := {a};

and, in action:

monoSplit@{1, 2, 4, 5, 7, 11, 8, 7, 3, 1, -3, -2, 6, 7, 80}//List
(* Out *) {{1, 2, 4, 5, 7, 11}, {8, 7, 3, 1, -3}, {-2, 6, 7, 80}}

Answer 5

Basically the same method I used for Partitioning a list when the cumulative sum exceeds 1.

As there my emphasis is on elegance rather than ultimate performance.

Cleaner now!

fn[a_List] :=
  Module[{o},
    Split[a, o # < o #2 || (o = #2 - #) &]
  ]

{1, 2, 4, 5, 7, 11, 8, 7, 3, 1, -3, -2, 6, 7, 80} // fn

{{1, 2, 4, 5, 7, 11}, {8, 7, 3, 1, -3}, {-2, 6, 7, 80}}

Answer 6

A solution using Compile

cfu3 = Compile[
  {{ints, _Integer, 1}},
  Block[{prev, next, startSeq, bag, sign},
   sign = 1;
   startSeq = ints[[1]];
   prev = startSeq;
   bag = Internal`Bag[{1}];
   Do[
    next = ints[[ii]];
    If[
     sign*next < sign*prev,
     Internal`StuffBag[bag, ii];
     sign *= -1;
     ];
    prev = next
    ,
    {ii, 2, Length@ints}
    ];
   Internal`BagPart[bag, All]
   ]
  ,
  CompilationTarget -> "C"
  ]

monotoneSequences[list_] := 
 Module[{starts, ends, maxDiff, maxDiffPos, longestStart},
  starts = cfu3[list];
  ends = starts + 
    Append[Differences[starts] - 1, Length[list] - starts[[-1]]];
  MapThread[list[[# ;; #2]] &, {starts, ends}]
  ]

Which gives

monotoneSequences[list]

{{1,2,4,5,7,11},{8,7,3,1,-3},{-2,6,7,80}}

Use cfu (instead of cfu3) from this answer to get only the ascending sequences.