Re: Re: position of sequence of numbers in list

*To*: mathgroup at smc.vnet.net*Subject*: [mg107014] Re: [mg107007] Re: position of sequence of numbers in list*From*: Leonid Shifrin <lshifr at gmail.com>*Date*: Sun, 31 Jan 2010 07:54:00 -0500 (EST)*References*: <hk17lo$ogf$1@smc.vnet.net> <201001311058.FAA10838@smc.vnet.net>

Hi Steve, I greatly enjoyed your solution. It is so much more elegant and more efficient than what I tried to do with Compile. I did some timings: In[1]:= largeTest = RandomInteger[{1, 12}, 300000]; In[2]:= Replace[ largeTest , {u___, 3, 4, 5, 6, ___} :> Length[{u}] + 1] // Timing Out[2]= {0.05, 48265} In[3]:= Position[Partition[largeTest , 4, 1], {3, 4, 5, 6}, 1, 1] // Timing Out[3]= {0.461, {{48265}}} It can be easily generalized to find all occurrences of the sequence, by using ReplaceList. In[4]:= Position[Partition[largeTest , 4, 1], {3, 4, 5, 6}] // Timing Out[4]= {0.951, {{48265}, {53605}, {53846}, {61161}, {108323}, \ {108993}, {112560}, {115757}, {127582}, {142593}, {197069}, {210130}, \ {254725}}} In[5]:= ReplaceList[ largeTest , {u___, 3, 4, 5, 6, ___} :> Length[{u}] + 1] // Timing Out[5]= {0.48, {48265, 53605, 53846, 61161, 108323, 108993, 112560, 115757, 127582, 142593, 197069, 210130, 254725}} And it is still twice more efficient than Position[Partition ... solution (it is interesting that Position can catch up by just being told that we search only level 1). By the way, it is a little off-topic, but this seems a more general technique, which has a great potential for efficient solutions (perhaps this is obvious to many people but I learned this relatively recently). I used the same technique to implement a fast tic-tac-toe solution finder in just a few lines of code, which checks for a winner on the infinite board and beats my Java implementation: ClearAll[winner]; winner[positions : {{{_Integer, _Integer} ..}, {{_Integer, _Integer} \ ..}}, wLen_] := Module[{pGen, diagF, analyze}, pGen = {___, Sequence @@ Table[#, {wLen - 1}], ___} &; diagF[x_, sign_] := x[[Ordering[x[[All, 1]] + sign*x[[All, 2]]]]]; analyze[points_] := Catch@With[{srt = Sort[points], pt = pGen /@ {{0, 1}, {0, 1}, {1, -1}, {1, 1}}}, MapThread[If[MatchQ[Differences@#1, #2], Throw["Winner"]] &, {{srt, Sort[points[[All, {2, 1}]]], diagF[srt, 1], diagF[srt, -1]}, pt}];]; Map[analyze, positions] /. {{"Winner", "Winner"} :> "A tie", {"Winner", Null} :> "Crosses win", {Null, "Winner"} :> "Nulls win", {Null, Null} :> "Nobody won yet"}]; It accepts a board represented as two sub-lists of 2-d coordinates for nulls and crosses, and the length of the winning combination. It runs 1000000 points (no-win situation) under 10 seconds on my not very fast machine, and beats my Java implementation which is 10 times more code and not the slowest possible either. Anyways, nice solution, thanks for sharing! Regards, Leonid On Sun, Jan 31, 2010 at 2:58 AM, Steve Luttrell <steve@_ removemefirst_luttrell.org.uk> wrote: > I don't know about efficiency, but here is another way of doing what you > want: > > {1, 2, 3, 4, 5} /. {u___, 3, 4, ___} :> Length[{u}] + 1 > > -- > Stephen Luttrell > West Malvern, UK > > "JB" <jkerrb at gmail.com> wrote in message news:hk17lo$ogf$1 at smc.vnet.net... > > Hi, > > > > What is the most efficient way to find the position of the beginning > > of a sequence of numbers from a list? > > > > I found a couple of ways: > > > > find 3,4 in list={1,2,3,4,5}; > > > > 1. pos=Intersection[Position[list,3],(Position[list,4])+1] > > > > 2. pos=Position[Partition[list,2,1],{3,4}] > > > > Are there other ways to do this? > > What is the best way when dealing with large lists? > > > > Thanks, > > JB > > > > >

**References**:**Re: position of sequence of numbers in list***From:*"Steve Luttrell" <steve@_removemefirst_luttrell.org.uk>