Services & ResourcesWolfram ForumsMathGroup Archive

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

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>