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

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).

• Also are you looking for strictly monotonic subsequences? Could there be repeated elements? If so, would they result in a split or not? – Martin Ender Apr 28 '16 at 9:02
• What output do you expect for {1, 2, 3, 1, 2, 3}? Will you rely on sequences alternating between increasing and decreasing (which would probably yield {{1, 2, 3}, {1}, {2, 3}}) or do you want to just pick monotonic sequences greedily (resulting in {{1, 2, 3}, {1, 2, 3}})? – Martin Ender Apr 28 '16 at 10:06
• ah..It's lapsus calami...-2 is not part of the second sequence..2 is less than 3 does not mean -2 is less than -3...I feel foolish.. – Harry Apr 28 '16 at 10:47
• there could be repeated elements and I will not split at repeated elements unless it is a max or min value. – Harry Apr 28 '16 at 10:49
• both {{1, 2, 3}, {1}, {2, 3}} and {{1, 2, 3}, {1, 2, 3}} are fine, but I'm prefer {{1, 2, 3}, {1, 2, 3}}.. – Harry Apr 28 '16 at 10:51

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.

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 *)


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}} *)


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}}


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}}


A solution using Compile

cfu3 = Compile[
{{ints, _Integer, 1}},
Block[{prev, next, startSeq, bag, sign},
sign = 1;
startSeq = ints[[1]];
prev = startSeq;
bag = InternalBag[{1}];
Do[
next = ints[[ii]];
If[
sign*next < sign*prev,
InternalStuffBag[bag, ii];
sign *= -1;
];
prev = next
,
{ii, 2, Length@ints}
];
InternalBagPart[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.