11
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Closely related: (23454) $\endgroup$ – Mr.Wizard Apr 30 '14 at 7:19
14
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! Is there any way how to find the position of the pattern in the list? $\endgroup$ – holistic Apr 20 '14 at 14:50
  • $\begingroup$ @holistic Yes, this is easily possible. Please see my edit in the answer. $\endgroup$ – halirutan♦ Apr 20 '14 at 17:41
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks rasher! Since I also want to search larger lists..this is very helpful!! $\endgroup$ – holistic Apr 21 '14 at 8:56
  • $\begingroup$ @holistic: Glad you find it useful. Thanks again for one of those "simple" but interesting problems! $\endgroup$ – ciao Apr 24 '14 at 0:22
  • $\begingroup$ 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 $\endgroup$ – Jacob Akkerboom Apr 24 '14 at 10:56
  • $\begingroup$ @JacobAkkerboom: Not even sure what that means, other than I have too much spare time ;-) but thanks! $\endgroup$ – ciao Apr 24 '14 at 22:35

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.