# position of sequence of elements in list [duplicate]

Possible Duplicate:
Finding a subsequence in a list

Question

The position of {3, 5} is the list

{1, 3, 4, 3, 5, 5, 1}


is 3. How can such a position be found fast when dealing with large lists?

Attempt

This is what I could think of:

list = Table[RandomInteger[3], {200}]
ToString[FromDigits[%]]
StringPosition[%, "123"][[1, All]]


Out put example:

{1, 3, 2, 3, 1, 2, 2, 0, 0, 1, 0, 2, 3, 0, 2, 1, 2, 2, 3, 3, 1, 0, 1,
3, 1, 1, 0, 3, 1, 3, 2, 2, 2, 1, 2, 0, 2, 0, 2, 2, 3, 1, 3, 1, 1, 1,
1, 3, 3, 1, 3, 1, 0, 2, 3, 1, 0, 3, 2, 3, 0, 1, 1, 3, 3, 3, 2, 1, 3,
0, 1, 0, 1, 0, 3, 1, 1, 2, 0, 0, 2, 0, 1, 3, 1, 2, 0, 2, 0, 2, 2, 2,
2, 2, 3, 1, 0, 3, 1, 2, 0, 3, 3, 2, 3, 1, 2, 3, 0, 0, 1, 2, 1, 2, 3,
2, 0, 1, 3, 1, 1, 1, 3, 2, 3, 3, 2, 0, 2, 3, 0, 3, 0, 3, 3, 2, 3, 2,
3, 1, 0, 1, 3, 0, 1, 1, 2, 2, 1, 2, 3, 3, 2, 3, 0, 2, 0, 3, 3, 2, 2,
0, 2, 3, 3, 2, 2, 0, 2, 2, 2, 3, 1, 3, 2, 0, 2, 0, 3, 3, 1, 0, 1, 2,
1, 2, 0, 0, 1, 0, 1, 0, 0, 2, 0, 3, 2, 1, 2, 2}

"132312200102302122331013110313222120202231311113313102310323011333213
0101031120020131202022222310312033231230012123201311132332023030332323
1013011221233230203322023322022231320203310121200101002032122"

{106, 108}


My solution does not work if the numbers in the list exceed 9 because there is no distinction between {..., 1, 2,...} and {...., 12, ....}. I also run into trouble if the sequence happens to start with 0.

I can fix this, but I doubt whether it is worth spending time on. There is likely a method that is faster in principle.

-

## marked as duplicate by Mr.Wizard♦Aug 2 '12 at 16:48

The fastest solution I know is the seqposC function from this answer. There was also the same question asked on StackOverflow before, with several nice answers posted there. –  Leonid Shifrin Jul 31 '12 at 16:03
I don't follow the logic... how is {3,5} in position 3? –  rm -rf Jul 31 '12 at 16:47
@R.M {3} occurs at positions 2 and 4. {5, 5} occurs at position 5 (till 6). Is it clear? How would you describe what I want to do? –  sjdh Aug 1 '12 at 8:40
I still don't get what you want to do... you said: "the position of {3, 5} is[sic] the list ... is 3". How is it 3? Your explanation above is something different (and how I would've understood it, had you not posted something else in the question). –  rm -rf Aug 1 '12 at 9:23
@R.M Sorry {3,5} is in position 4 and not at 3 indeed. –  sjdh Aug 2 '12 at 11:16

This isn't particularly fast, but I like it for simplicity:

seqpos[a_List, seq_List] :=
ReplaceList[a, {x___, Sequence @@ seq, ___} :> 1 + Length[{x}]]

seqpos[{1, 2, 3, 4, 2, 3}, {2, 3}]
(* {2,5} *)

-

Here is a faster variation of the seqposC function from this answer:

seqposCB =
Compile[{{list, _Integer, 1}, {seq, _Integer, 1}},
Module[{i = 1, j = 1, res = InternalBag[0],len = Length[list], slen = Length[seq]},
Do[
If[CompileGetElement[list, i] == CompileGetElement[seq, 1],
While[j < slen && i + j <= len &&
CompileGetElement[list, i + j] == CompileGetElement[seq, j + 1],
j++
];
If[j == slen, InternalStuffBag[res, i]]; j = 1;],
{i, 1, len}
];
Rest@InternalBagPart[res, All]
],
CompilationTarget -> "C", RuntimeOptions -> "Speed"]


Some benchmarks:

digs = RealDigits[N[Pi, 5000000]][[1]];
Do[seqposCB[digs,{1,2,3,4,5}],{50}]//AbsoluteTiming

(* {0.7089843,Null} *)


This is the fastest way I know to do this in Mathematica (if the sequence you are after is also very long, there may be faster algorithms, based e.g. on rolling hashes, but those are considerably more complex).

-
Thus this work in Mathematica 7? Mathematica returns "Unknown option compilation target in compile[....]" –  sjdh Aug 1 '12 at 8:51

This might work to:

data = RandomInteger[{1, 20}, 100]


Out:

{17, 14, 3, 10, 7, 3, 7, 19, 6, 6, 3, 2, 5, 2, 15, 12, 7, 9, 18, 1, \
6, 9, 2, 4, 16, 16, 5, 15, 11, 8, 9, 13, 19, 14, 20, 19, 17, 15, 14, \
14, 9, 12, 2, 14, 17, 13, 9, 1, 6, 13, 11, 5, 19, 8, 16, 12, 8, 1, 5, \
18, 1, 13, 17, 11, 18, 1, 2, 6, 6, 3, 10, 4, 2, 17, 9, 2, 5, 10, 7, \
8, 17, 4, 6, 5, 19, 3, 10, 3, 6, 14, 19, 16, 15, 20, 11, 10, 7, 20, \
9, 11}


Find first position of sequence {16,16}

Position[Partition[data, 2, 1], {16, 16}]


Out:

{{25}}

data[[25;;26]]


Out:

{16,16}
`

Absolute Timing gave for a dataset of 5000000 numbers 1.82 seconds.

-