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$
  • $\begingroup$ Do you want the position as well? The Accepted answer does not provide this. Was i only for notation? $\endgroup$ – Mr.Wizard Aug 7 '14 at 20:31
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$
  • 2
    $\begingroup$ In V10 there is also SelectFirst[Partition[list, 2, 1], Not@*OrderedQ] $\endgroup$ – C. E. Aug 7 '14 at 19:20
  • $\begingroup$ @Pickett Those composition shorthands are quite nice; I should upgrade at some point :). $\endgroup$ – Teake Nutma Aug 7 '14 at 19:22
  • $\begingroup$ Thanks, I forgot about this use of Partition. $\endgroup$ – John McGee Aug 7 '14 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
    $\begingroup$ I minor detail: you don't need b in b___. By the way I like this answer best. :-) $\endgroup$ – Mr.Wizard Aug 7 '14 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, privacy policy and cookie policy

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