Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
Do you want the position as well? The Accepted answer does not provide this. Was i only for notation? –  Mr.Wizard Aug 7 at 20:31

5 Answers 5

up vote 4 down vote accepted

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.

share|improve this answer
2  
In V10 there is also SelectFirst[Partition[list, 2, 1], Not@*OrderedQ] –  Pickett Aug 7 at 19:20
    
@Pickett Those composition shorthands are quite nice; I should upgrade at some point :). –  Teake Nutma Aug 7 at 19:22
    
Thanks, I forgot about this use of Partition. –  John McGee Aug 7 at 19:29

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]
share|improve this answer

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} *)
share|improve this answer
1  
+1 for including the position. –  RunnyKine Aug 7 at 19:42
1  
I minor detail: you don't need b in b___. By the way I like this answer best. :-) –  Mr.Wizard Aug 7 at 20:36

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}}
share|improve this answer
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} *)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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