5
$\begingroup$

I would like to know how to efficiently determine the first pair of elements in a list that are not in order according to some predicate p. That is, list[i] > list[j] according to p, and i is the smallest index for which this is true. It is easy, but gauche, using nested loops.

$\endgroup$
1
  • $\begingroup$ Do you want the position as well? The Accepted answer does not provide this. Was i only for notation? $\endgroup$
    – Mr.Wizard
    Commented Aug 7, 2014 at 20:31

6 Answers 6

6
$\begingroup$

Given this test list

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

we can extract the first pair of elements that are not increasing as follows:

Select[Partition[list, 2, 1], ! Less @@ # &, 1]
{{4,3}} 

For other predicates you can adjust the second argument of Select accordingly.

$\endgroup$
3
  • 2
    $\begingroup$ In V10 there is also SelectFirst[Partition[list, 2, 1], Not@*OrderedQ] $\endgroup$
    – C. E.
    Commented Aug 7, 2014 at 19:20
  • $\begingroup$ @Pickett Those composition shorthands are quite nice; I should upgrade at some point :). $\endgroup$ Commented Aug 7, 2014 at 19:22
  • $\begingroup$ Thanks, I forgot about this use of Partition. $\endgroup$
    – John McGee
    Commented Aug 7, 2014 at 19:29
3
$\begingroup$

In V10 There's FirstCase:

FirstCase[Partition[list, 2, 1], {x_, y_} /; x > y]

Otherwise:

Cases[Partition[list, 2, 1], {x_, y_} /; x > y, 1, 1]
$\endgroup$
3
$\begingroup$

Pattern-matching approach:

{1, 2, 3, 4, 3, 4, 5, 6} /. {a___, x_, y_, b___} /; x > y :> {Length[{a}] + 1, {x, y}}
(* {4, {4, 3}} *)

That means 4>3 at the 4th position in the list.


Another less elegant approach:

greaterQ = (Last@Take[list, #] > First@Drop[list, #] & /@ Range[Length@list - 1])~Append~False
(* {False, False, False, True, False, False, False, False} *)

p = Position[greaterQ, True]
(* {{4}} *)

list[[Flatten@{p, p + 1}]]
(* {4, 3} *)
$\endgroup$
1
  • 1
    $\begingroup$ I minor detail: you don't need b in b___. By the way I like this answer best. :-) $\endgroup$
    – Mr.Wizard
    Commented Aug 7, 2014 at 20:36
3
$\begingroup$

A method using LengthWhile:

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

x = First @ list;
p = Less;
1 + LengthWhile[Rest @ list, p[x, x = #] &]
{list[[%]], x}
4

{4, 3}

This gives the index and then the pair itself. As a function:

f[l : {a_, b__}, p_] :=
 Module[{x = a},
   1 + LengthWhile[{b}, p[x, x = #] &] //
     {#, {l[[#]], x}} &
 ]

f[{9, 8, 7, 6, 7, 6, 5, 4}, Greater]
{4, {6, 7}}
$\endgroup$
2
$\begingroup$
list = {1, 2, 3, 4, 3, 2, 4, 5, 6, 4, 3};

sl = Split[list, Greater];
Select[sl, Length[#] >= 2 &, 1][[1, ;; 2]]
Cases[sl, {x_, y_, ___} :> {x, y}, 1, 1][[1]]
Pick[sl, Length[#] >= 2 & /@ sl][[1, ;; 2]]
sl[[LengthWhile[sl, Length[#] == 1 &] + 1, ;; 2]]
sl[[LengthWhile[sl, OrderedQ] + 1, ;; 2]]
Extract[Split[list, Less], {{1, -1}, {2, 1}}]

all give

(* {4, 3} *)
$\endgroup$
0
$\begingroup$

New in V10.1, SequenceCases.

list = {1, 2, 3, 4, 3, 4, 5, 6}
SequenceCases[list, {a_, b_} /; a > b, 1]

{{4, 3}}

$\endgroup$

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.