Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: finding the position of a pattern in list

• To: mathgroup at smc.vnet.net
• Subject: [mg64632] Re: [mg64583] finding the position of a pattern in list
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Fri, 24 Feb 2006 00:18:51 -0500 (EST)
• References: <200602230534.AAA13180@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Gang Ma wrote:
> Hi,
> I am working on a program to do the following: My data is a list of 0  
> and 1. For example, {0,0,1,1,1,0,0,1,1,1,0}. I want to find the  
> positions of all the pattern of {0,1}.  In my previous example, the  
> first {0,1} is at 2 and and the second {0,1} appears at 7. I can  
> write a loop to do this, but I have several thousands such lists,   
> the computation will be time consuming using loop.
> 
> My question is whether it is possible to use the pattern match to do  
> this quickly.  If not for the list, do I need to convert the list to  
> string then use some pattern match for string?  Thank you very much.
> 
> regards,
> 
> Gang Ma

Here are a couple of possibilities. They assume without checking that 
the list has at least one entry and all entries are zero or one.

zeroOneTransitions1[ll_List] :=
   Take[#,{If[ll[[1]]==0,1,2],Length[#]-1,2}]& [
     Rest[FoldList[Plus,0,Map[Length,Split[ll]]]]]

zeroOneTransitions2[ll_List] :=
   Flatten[Position[Partition[ll,2,1],{0,1}]]

It appears the first is a bit faster once lists are not small.

ll = Table[Random[Integer], {10}];

In[4]:= Timing[Do[zeroOneTransitions1[ll], {10^5}]]
Out[4]= {2.44015 Second, Null}

In[5]:= Timing[Do[zeroOneTransitions2[ll], {10^5}]]
Out[5]= {2.49216 Second, Null}

ll = Table[Random[Integer], {10^2}];

In[7]:= Timing[Do[zeroOneTransitions1[ll], {10^4}]]
Out[7]= {0.704044 Second, Null}

In[8]:= Timing[Do[zeroOneTransitions2[ll], {10^4}]]
Out[8]= {0.948059 Second, Null}

ll = Table[Random[Integer], {10^3}];

In[10]:= Timing[Do[zeroOneTransitions1[ll], {10^3}]]
Out[10]= {0.532034 Second, Null}

In[11]:= Timing[Do[zeroOneTransitions2[ll], {10^3}]]
Out[11]= {0.96806 Second, Null}


Daniel Lichtblau
Wolfram Research

• References:
  • finding the position of a pattern in list
    • From: Gang Ma <contactmagang@gmail.com>