# First pair out of order

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.

• Do you want the position as well? The Accepted answer does not provide this. Was i only for notation? Commented Aug 7, 2014 at 20:31

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.

• In V10 there is also SelectFirst[Partition[list, 2, 1], Not@*OrderedQ] Commented Aug 7, 2014 at 19:20
• @Pickett Those composition shorthands are quite nice; I should upgrade at some point :). Commented Aug 7, 2014 at 19:22

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]


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

• I minor detail: you don't need b in b___. By the way I like this answer best. :-) Commented Aug 7, 2014 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}}

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


New in V10.1, SequenceCases.

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


{{4, 3}}