6
$\begingroup$

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

$\endgroup$
1

7 Answers 7

9
$\begingroup$

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} *)
$\endgroup$
1
  • $\begingroup$ Thank you very much! $\endgroup$ Jun 28, 2023 at 11:46
9
$\begingroup$

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}*)
$\endgroup$
1
  • 2
    $\begingroup$ Neat and surprising $\endgroup$
    – eldo
    Sep 21, 2023 at 22:24
5
$\begingroup$

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} *)
$\endgroup$
5
$\begingroup$

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

enter image description here

$\endgroup$
4
$\begingroup$

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 /@ %

enter image description here


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]

enter image description here

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

A late and simple answer:

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

Union @ FoldList[Max] @ list

{1, 2, 4, 8}

Example data from earlier answers:

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

enter image description here

$\endgroup$
0
$\begingroup$

You can say:

l2new = Split[l2, Greater][[All,1]]
$\endgroup$
2
  • 1
    $\begingroup$ I like trying to use Split, but this doesn't work. Test it with l3. $\endgroup$
    – lericr
    Jun 28, 2023 at 8:51
  • 1
    $\begingroup$ try replacing Split with Gather? $\endgroup$
    – kglr
    Jun 28, 2023 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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