# Dropping disordered numbers in a list

I have a list of numbers like l1 = (1,2,3,4,8) and clearly, l1 is in order (next number is greater than previous number).

Well, I have a list of l2 = {1,2,4,3,8}. Because 3 is not in order, I want to drop 3 so that I have a new list of l2new = {1,2,4,8} which is now in order.

What is the algorithm to have l2new from l2?

To clarify my purpose, I introduce another example: If I have l3 = {1,2,8,4,5}, then I want to have l3new = {1,2,8}.

Maybe something like this:

IncreasingSubset[list_] :=
Fold[If[#2 >= Last[#1], Append[#1, #2], #1] &, {First@list}, Rest@list]


Try it:

IncreasingSubset[l3]
(* {1, 2, 8} *)

• Thank you very much! Jun 28, 2023 at 11:46

Another way is as follows:

ddlist[lst_] := Tally[lst, #2 <= #1 &][[All, 1]]


Test:

l2 = {1, 2, 4, 3, 8};
l3 = {1, 2, 8, 4, 5};
l4 = {1, 2, 5, 3, 4, 6};
ddlist[l2]
(*{1, 2, 4, 8}*)
ddlist[l3]
(*{1, 2, 8}*)
ddlist[l4]
(*{1, 2, 5, 6}*)

• Neat and surprising
– eldo
Sep 21, 2023 at 22:24

One way, probably not the most efficient:

ddb[alist_] :=
FoldPair[{If[#1[[-1]] <= #2, Join[#1, {#2}], #1],
If[#1[[-1]] <= #2, Join[#1, {#2}], #1]} &, alist[[1 ;; 1]],
alist[[2 ;;]]]


Checks:

ddb[{1, 2, 3, 4, 8}]
(* {1, 2, 3, 4, 8} *)
ddb[{1, 2, 4, 3, 8}]
(* {1, 2, 4, 8} *)
ddb[{1, 2, 8, 4, 5}]
(* {1, 2, 8} *)


Perhaps:

f[u_] := u //. {a___, b_, c_, d___} /; b > c :> {a, b, d}


For, example:

Column[# -> f@# & /@ {{1, 2, 4, 3, 8}, {1, 2, 8, 4, 5, 12}, {1, 2, 8,
4, 5, 6, 12}, {2, 1}, {2, 1, 3, 4}}]


First a test case:

All troughs need to be removed from the sublists. The following will provide a visual feedback.

FixedPointList[
First /@ Split[#, Greater] &, {1, 2, 4, 3, 8, 6, 10, 11, 7, 10}]
ListLinePlot /@ %


Using FixedPoint:

lists = {{1, 2, 3, 4, 8}, {1, 2, 4, 3, 8}, {1, 2, 8, 4, 5}, {1, 2, 5,
3, 4, 6}, {2, 1}, {2, 1, 3, 4}, {1, 2, 4, 8, 5, 12}, {1, 2, 4, 3,
8, 6, 10, 11, 7, 10}};

{# -> FixedPoint[First /@ Split[#, Greater] &, #] & /@ lists } //
Map[Column]


• lists has elements that have been borrowed from other answers on the page with thanks.
– Syed
Jun 28, 2023 at 11:47

list = {1, 2, 4, 3, 8};

Union @ FoldList[Max] @ list


{1, 2, 4, 8}

lists = {{1, 2, 3, 4, 8}, {1, 2, 4, 3, 8}, {1, 2, 8, 4, 5}, {1, 2, 5,
3, 4, 6}, {2, 1}, {2, 1, 3, 4}, {1, 2, 4, 8, 5, 12}, {1, 2, 4, 3,
8, 6, 10, 11, 7, 10}};

# -> Union @ FoldList[Max, #] & /@ lists // Column


You can say:

l2new = Split[l2, Greater][[All,1]]

• I like trying to use Split, but this doesn't work. Test it with l3. Jun 28, 2023 at 8:51
• try replacing Split with Gather?
– kglr
Jun 28, 2023 at 18:54