Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I have a list in the form :

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

No I'm trying to select only those sequences which start with 1 have a zero (or many zeros) between and are followed by -1. For example: 1,0,-1 | 1,0,0,0,0,-1

I tried to use Cases, but I'm not sure how to define the pattern. Can someone help me out please?

share|improve this question
    
+1 for an interesting question –  rasher Apr 21 at 3:00
    
Closely related: (23454) –  Mr.Wizard Apr 30 at 7:19
add comment

2 Answers 2

up vote 11 down vote accepted

One way is this

ReplaceList[{1, 1, 1, 0, -1, -1, 1, 1, 1, 0, 0, 0, 0, -1, -1}, 
  {___, a : PatternSequence[1, 0 .., -1], ___} :> {a}]

(* {{1, 0, -1}, {1, 0, 0, 0, 0, -1}} *)

If you need the position, length or some other information about the location of the match inside the list, you could do it like this:

ReplaceList[{1, 1, 1, 0, -1, -1, 1, 1, 1, 0, 0, 0,  0, -1, -1}, 
 {s___, a : PatternSequence[1, 0 .., -1], ___} :> 
  With[{l = Length[{s}]}, {{l + 1, l + Length[{a}]}, {a}}]]

(* {{{3, 5}, {1, 0, -1}}, {{9, 14}, {1, 0, 0, 0, 0, -1}}} *)

This stores the start elements before the matching pattern in s and you can calculate all information from this. Here, I give the start- and end-position of the pattern inside the list.

share|improve this answer
    
Thanks! Is there any way how to find the position of the pattern in the list? –  holistic Apr 20 at 14:50
    
@holistic Yes, this is easily possible. Please see my edit in the answer. –  halirutan Apr 20 at 17:41
add comment

Be aware, the method posted by halirutan, while concise, will be glacially slow on larger lists. Here's a method whipped up cigar-thinking that is much faster. Just a WIP, there's probably 2-3X performance improvement left in it (e.g., using something other than membership testing), but again, just barfed this out during leisure time (edit, updated code, much faster, will update timings from older code as patience permits):

getSeq3[list_] := 
 Module[{z = Split[Select[Pick[Range@Length@list, list, 0], 
                          1 < # < Length@list &], #2 == #1 + 1 &][[All, {1, -1}]]},

  {# + {-1, 1}, list[[#[[1]] - 1 ;; #[[2]] + 1]]} & /@ 
   Select[z, (list[[#[[1]] - 1]] == 1 && list[[#[[2]] + 1]] == -1) &]]

A quick timing comparison (lists generated with RandomInteger[{-1,1},size], on a netbook so expect 10-20X faster on "real" machines):

enter image description here

Updated timings from improvements:

enter image description here

An even faster result can be had by moving things into the string domain:

getSeqSP[list_] := 
 Module[{sp = StringPosition[FromCharacterCode[list + 2], 
               FromCharacterCode[3] ~~ Repeated[FromCharacterCode[2], {1, Infinity}] ~~ 
                                       FromCharacterCode[1]]},

  Transpose[{sp, Rest@Extract[list, Prepend[Transpose[{Span @@@ sp}], {{}}]]}]]

Timings are so quick, even on the netbook they are below resolution:

enter image description here

On larger lists, this is order of magnitude + faster than already fast methods above. Probably about as fast as possible without resorting to compiled methods.

share|improve this answer
    
Thanks rasher! Since I also want to search larger lists..this is very helpful!! –  holistic Apr 21 at 8:56
    
@holistic: Glad you find it useful. Thanks again for one of those "simple" but interesting problems! –  rasher Apr 24 at 0:22
    
Congrats on having top rep this quarter, as well having 7,666 rep, which is a nice number :P. Nice tables here too, ratios of timings are a good thing. +1 –  Jacob Akkerboom Apr 24 at 10:56
    
@JacobAkkerboom: Not even sure what that means, other than I have too much spare time ;-) but thanks! –  rasher Apr 24 at 22:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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