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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Do you want the position as well? The Accepted answer does not provide this. Was i only for notation? $\endgroup$– Mr.WizardAug 7, 2014 at 20:31
Add a comment
|
6 Answers
$\begingroup$
$\endgroup$
3
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.
answered Aug 7, 2014 at 19:18
-
2$\begingroup$ In V10 there is also
SelectFirst[Partition[list, 2, 1], Not@*OrderedQ]$\endgroup$– C. E.Aug 7, 2014 at 19:20 -
$\begingroup$ @Pickett Those composition shorthands are quite nice; I should upgrade at some point :). $\endgroup$ Aug 7, 2014 at 19:22
-
$\begingroup$ Thanks, I forgot about this use of Partition. $\endgroup$ Aug 7, 2014 at 19:29
$\begingroup$
$\endgroup$
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]
answered Aug 7, 2014 at 19:25
$\begingroup$
$\endgroup$
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} *)
answered Aug 7, 2014 at 19:25
-
1$\begingroup$ I minor detail: you don't need
binb___. By the way I like this answer best. :-) $\endgroup$ Aug 7, 2014 at 20:36
$\begingroup$
$\endgroup$
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}}
answered Aug 7, 2014 at 20:44
$\begingroup$
$\endgroup$
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} *)
$\begingroup$
$\endgroup$
New in V10.1, SequenceCases.
list = {1, 2, 3, 4, 3, 4, 5, 6}
SequenceCases[list, {a_, b_} /; a > b, 1]
{{4, 3}}
