# Find positions of items in a list based on neighbours

How can I select items from a list where the selection criterion depends on the neighbouring items?

For example select all indices where a change has occurred with respect to the previous element in the list:

u = {0,0,1,1,1,1,0,0,0,1,1,0,0,0,1};


Desired output:

r = {{3,+1},{7,-1},{10,+1},{12,-1},{15,+1}}


My current implementation looks like that:

process[u_] := Select[Table[If[u[[i]] != u[[i - 1]], {i, u[[i]] - u[[i - 1]]}, {}], {i, 2, Length@u}], Length@# != 0 &]


which is probably neither fast nor elegant and scales poorly when using multiple neighbours...

In this example I only need one neighbour (the previous item), but I would be interested in a solution where I can check a bigger neighbourhood too.

You wrote:

In this example I only need one neighbour (the previous item), but I would be interested in a solution where I can check a bigger neighbourhood too.

I missed that, and I think Simon and Kuba did too. While a numeric method such as those shown in the other answers will be far faster, here are some other, more generalized approaches.

As an example take this list of characters:

SeedRandom
list = RandomChoice[CharacterRange["a", "z"], 20]

{"f", "a", "h", "a", "c", "d", "a", "v", "a", "q", "x", "o", "d", "i",
"t", "f", "s", "q", "m", "a"}


And the task of finding the positions of every letter surrounded by two vowels. (Yes, this too could be converted to a faster numeric form but I couldn't think of a simple example that could not.)

We can Partition the list and then scan those partitions for a pattern:

vowel = Alternatives @@ Characters["aeiou"];
pat = {vowel, _, vowel};

pos = Position[Partition[list, 3, 1], pat]
Extract[list, pos + 1]

{{2}, {7}, {12}}

{"h", "v", "d"}


This is usually the simplest place to start and the many configuration options of Partition make it flexible and powerful. Nevertheless it can be memory-inefficient because you multiply the length of list in the partition operation. Further, you can't exit early from the Partition operation, should you wish to do that. See How to find first list element that differs from average of N previous elements by more than a given amount? for an exploration of these issues and alternatives.

Explicitly looping over the list can be more memory-efficient:

Table[If[MatchQ[list[[i ;; i + 2]], pat], i, ## &[]], {i, 1, Length@list - 2}]

{2, 7, 12}


(See this post for an explanation of ## &[].) More craftily you might employ Sow and Reap:

Reap[Do[Sow[i, {list[[i ;; i + 2]]}], {i, 1, Length@list - 2}], {pat}][[2, 1]]

{{2}, {7}, {12}}


Finally, more elegantly you can use ReplaceList, but be careful to check its performance in your application as depending on the pattern it may scale very poorly:

ReplaceList[list, {x___, vowel, _, vowel, ___} :> 1 + Length@{x}]

{2, 7, 12}


This method comes from Finding a subsequence in a list and the referenced answer by Jan Pöschko before it.

• The trick with ## &[] is very good to know! Feb 9 '14 at 17:13
Append @@@ Most[ArrayRules[{0}~Join~Differences[u]]]

(* {{3, 1}, {7, -1}, {10, 1}, {12, -1}, {15, 1}} *)

• Simon, I know that at least one other question is very similar to this one, specifically about selecting and/or positions with a pattern that includes neighboring elements. Would you help me look for it? Feb 8 '14 at 12:56
• Well, I can't find a duplicate, and this is a very nice method, so +1. :-) Feb 8 '14 at 13:20
• @Mr.Wizard, sorry I wasn't ignoring your request, I had to pop out. I can't find a duplicate either. Feb 8 '14 at 14:01

Same idea as Simon's answer, but using lower-level SparseArray Properties for greater efficiency:

SparseArray[Differences[u] ~Prepend~ 0] /@

{{3, 1}, {7, -1}, {10, 1}, {12, -1}, {15, 1}}


Speed comparison in version 7:

u = RandomInteger[{-1, 1}, 2500000];

Append @@@ Most[ArrayRules[{0}~Join~Differences[u]]] // AbsoluteTiming // First

SparseArray[Differences[u] ~Prepend~ 0] /@
{"AdjacencyLists", "NonzeroValues"} // Transpose // AbsoluteTiming // First

1.0480599

0.0610035

MapIndexed[
If[# == 0, Unevaluated[], {#2[] + 1, #}] &,
Differences@u]

{{3, 1}, {7, -1}, {10, 1}, {12, -1}, {15, 1}}

• nice use of MapIndexed. since all the good answers are shown, I tried this in Matlab to see how it will look like, here is the answer: !Mathematica graphics Matlab does not have pure functions (at least not as they work in Mathematica) Feb 8 '14 at 13:24
• @Nasser Thanks. Well I do not know Matlab, but your code in Mathematica would be with Positions as equivalent function to find, wouldn't it be?
– Kuba
Feb 8 '14 at 13:56
• Use, Position and find() are similar in this case (I've solved this also in M using Position and Cases, but solutions shown here are nicer than what I have). Matlab's find() actually is more flexible than M's Position[]. I mentioned this before, as it can return more information than just the position, it also can return the corresponding values found at those positions. In M, one has to use Positions and then use Extract. Here is Matlab's help on find() mathworks.com/help/matlab/ref/find.html May be in V10, they'll add an option to Position to do the same :) Feb 8 '14 at 14:15
• @Nasser Ah yes, I remember your question about that. I find find more useful too :)
– Kuba
Feb 8 '14 at 14:29