# How to use patterns to return non-overlapping sequences of consecutive elements from an array

Let me first describe the data structure I'm looking at before describing my question. I have an array of nx3 elements with a data-generating process such that each row has the format:

{previous row's Last element, new random integer, sum of previous row's last element and new random integer} (note: the first row's first element is constrained to be zero)

Here's a function to create such an array of some length n using a range of integers (e.g. {-10,10}):

randomArray[range_List, length_Integer]:=
Module[{
vals=RandomInteger[range, {length}],
totals
},
totals = FoldList[Plus, 0, vals];
Append[Rest@totals, Last@totals]}]
];


My question is how can I use PatternSequence[] to list out all cases of runs of consecutive elements. More specifically, I wish to find the shortest sequence of elements where the first row's last element is positive and thus has the pattern {_,_,_?Positive}. This will then be followed by zero or more elements with the same pattern and finally concluded with a row with the pattern {_,_,_?PossibleZeroQ}. So my code for what I thought would work is as follows:

Shortest[PatternSequence[{_, _, _?Positive}, ___, {_, _,
_?PossibleZeroQ}]]


...which could be applied to Cases[] at level 1 or ReplaceAll[] etc., but it does not return what I'm looking for.

For example, given the explicit test data structure given by:

data={{0, 1, 1}, {1, -1, 0}, {0, -6, -6}, {-6, 8, 2}, {2, 9, 11},
{11, 6, 17}, {17, -10, 7}, {7, 10, 17}, {17, 2, 19}, {19, -10, 9},
{9, 0, 9}};


...then I would expect to use...

Cases[data,
Shortest[PatternSequence[{_, _, _?Positive}, ___, {_, _,
_?PossibleZeroQ}]], {1}, 1]


...to return the first such pattern found as in

{{0, 1, 1}, {1, -1, 0}}


...but I only get {} returned.

My goal is to return a list of all such patterns, but as I only used Cases[] here to attempt to get the first pattern, it still did not work.

Am I using PatternSequence[] or something else incorrectly here or missing a pattern object such as Repeated or something like that? I appreciate any input on the matter.

I also realize that I can use Split[] or a close-cousin to perform this operation, but I would like to attempt to get the results if possible using pattern objects and pattern tests. Thank you!

• @march, thank you for the catch. I had done some other processing on my example data which caused the error. Using the provided randomArray[] function works to produce the correct structure however. Thanks for catching my error! I've made the edits. Nov 9, 2015 at 4:05
• I'm a little confused about this: "My question is how can I use PatternSequence[] to list out all cases of runs of consecutive elements. More specifically, I wish to find the shortest sequence of elements where the first row's last element is positive and thus has the pattern {_,_,_?Positive}". Is the first question what you actually want to do and the second one step on the way that helps you understand how to use PatternSequence? Nov 9, 2015 at 4:43
• A point of clarification: you want to "list out all cases of runs of consecutive elements". To me, that reads as "find sequences n, n+1, n+2, ..., which can only ever happen within one of your lists, and it can only be {0, 1, 2}. Do you mean runs of the same element (which is suggested by the code you're working on)? In that case, you can never get runs going over more than two lists, due to the summation, so why not remove the ___ between the lists in your pattern? Nov 9, 2015 at 5:36
• Hi @march, thanks for your help. To clarify, when I say "list out all cases", I'm saying the elements of the list will each be a "run", where a "run" is defined as a list whose elements are all of the form {_, _, _?Positive} except the last element, which should be in the form {_, _, _?PossibleZeroQ}. And further, the constraint I want to impose is that the sequence of elements of each "run" is the shortest possible consecutive sequence and are thus in the same order as the original data list. I hope that clarifies things somewhat. Nov 9, 2015 at 7:33
• In case you're interested, I think it's a good idea to post an answer using SequenceCases, if you were ever able to get that to work. I think it would be a useful addition to this Q&A. (I will upvote if you do: send me a comment if you do it.) Dec 28, 2015 at 17:53

Update

Based on OP's comments, here's how I would go about solving this problem pre-V10.1 (the OP is correct that SequenceCases is the best option here, but it was introduced in V10.1). We want to find all runs, where a "run" is defined as a sequence of elements in which the last element in the list is always positive, and the run ends when the last element in the list is 0. For the purposes of making sure things work out, I'm going to use the modified list

data = {{0, 1, 1}, {1, -1, 0}
, {0, -6, -6}
, {-6, 8, 2}, {2, 9, 11}, {11, 6, 17}, {17, -18, -1}
, {-1, 11, 10}, {10, -4, 6}, {6, -6, 0}
, {-1, 1, 0}
, {9, -9, 0}};


I've broken it up in this way to illustrate that there are some sequences that it shouldn't match and some that it should. It should match only the first and the fourth. The rest don't match the criterion of being all positive and ending in zero.

Here's what we do:

runs = Last@Reap[data //. {a___, pat : PatternSequence[{_, _, _?Positive} .., {_, _, 0}], b___} :> (Sow[{pat}]; {a, Unique[], b})]
(* {{{{0, 1, 1}, {1, -1, 0}}
, {{-1, 11, 10}, {10, -4, 6}, {6, -6, 0}}}} *)


The logic is as follows. We match a run to the sequence with the pattern

{a___, pat : PatternSequence[{_, _, _?Positive} .., {_, _, 0}], b___}


which uses the Repeated (..) pattern to indicate that there are repeated elements all matching {_, _, _?Positive}. We name the pattern pat so that we can Sow the resulting match and Reap it later. We use replacement rules to take out the matched bit so that it won't get matched again, replacing it with a Unique place-holder, and we use ReplaceRepeated to do this until we've found all of the runs.

Just to see what happens to the actual list:

First@Reap[data //. {a___, pat : PatternSequence[{_, _, _?Positive} .., {_, _, 0}], b___} :> (Sow[{pat}]; {a, Unique[], b})]
(* {$3, {0, -6, -6}, {-6, 8, 2}, {2, 9, 11}, {11, 6, 17}, {17, -18, -1},$4, {-1, 1, 0}, {9, -9, 0}} *)


The runs have been replaced by Unique variables $3 and $4, and the rest of the list remains unaltered.

Original Post

I think you need to embed the PatternSequence inside the list, like so:

{a___, pat : PatternSequence[{_, _, _?Positive}, {_, _, 0}], b___}


I'm going to take a slightly different take on this. I'm not entirely sure Cases is the best choice here, but what I'm about to show might not work either for the general case. I took the liberty of changing the last element of your list to illustrate that for this specific pattern, it will choose the Shortest automatically, because pattern-matching is automatically greedy from the end of the list (I think that's how that works). Anyway:

data = {{0, 1, 1}, {1, -1, 0}, {0, -6, -6}, {-6, 8, 2}, {2, 9, 11}, {11, 6, 17}, {17, -10, 7}, {7, 10, 17}, {17, 2, 19}, {19, -10, 9}, {9, -9, 0}};
Last@Reap[
data /. {a___, pat : PatternSequence[{_, _, _?Positive}, ___, {_, _, 0}], b___} :> (Sow[{pat}]; {a, pat, b})
]
(* {{{{0, 1, 1}, {1, -1, 0}}}} *)


Note that if we add Longest@ in front of PatternSequence, it returns the whole list, illustrating the "greediness-from-the-end" pattern-matching behavior.

For fun, here's another generator for your list:

randomArray[range_List, length_Integer] := With[{first = RandomInteger[range]}
, NestList[{#1, #2, #1 + #2} & @@ {Last@#, RandomInteger[range]} &, {0, first, first}, length - 1]
]


I'm definitely interested in the actual problem you want to solve, so please leave comments.

• thanks again. That's a good start. It may help also to show how I solved the problem using Split[]. I will apply it to the test data you have in this answer. Here is the code: Split[data, Sign[Last@#1] == Sign[Last@#2] || Sign[Last@#2] == 0 &] which gives {{{0, 1, 1}, {1, -1, 0}}, {{0, -6, -6}}, {{-6, 8, 2}, {2, 9, 11}, {11, 6, 17}, {17, -10, 7}, {7, 10, 17}, {17, 2, 19}, {19, -10, 9}, {9, -9, 0}}}. You'll notice this lists out each run as an element of the returned list. I will share more about my problem a bit later as I'm short on time now. Thanks again! Nov 9, 2015 at 10:09
• I may have stumbled upon the answer using SequenceCases[] and this very concise expression SequenceCases[data, {{_, _, _?Positive} .., {_, _, _?PossibleZeroQ}}]. I'll review tomorrow and revert. Nov 9, 2015 at 10:42
• I keep forgetting about SequenceCases since I only have Mathematica 10.0, and it was introduced in 10.1, but that's a good idea. Now that I understand what you are trying to do, I'll update my answer. But I recommend including the Split version in your question, just for completeness, or you can post an answer to your question, because why not? EDIT: one last point: why do you use _?PossibleZeroQ instead of just 0? Nov 9, 2015 at 21:01
• @rfrasier-mlp. I have posted an updated answer. Does it work? (I think it does.) Nov 9, 2015 at 21:40
• thank you again. I am using _?PossibleZeroQ honestly just for code readability, consistency in using PatternTest[], and robustness to so it can handle real-valued arrays so I don't forget to change it from 0 later :-) Nov 10, 2015 at 1:03