# Match a sequence of integers

I would to match a pattern

 p1 = 0,0,1,0,0


to the elements in listA. The elements are a boolean sequence that may look like this

 {{0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0}}


Every where p1 matches the sequence I want to change that part into

 p2 = .5, .5, 1, .5, .5


that will change listA into

 {{.5, .5, 1, .5, .5, 1, 0, 1, 1, .5, .5, 1, .5, .5},   {0, 0, .5, .5, 1, .5, .5, .5, .5, 1, .5, .5, 0, 0}}


Thanks!

• What with overlapping, {0,0,1,0,0,1,0,0}?
– Kuba
Aug 16, 2013 at 22:55
• Note that you cannot assign a raw sequence such as p1 = 0,0,1,0,0. You can use Sequence e.g. p1 = Sequence[0,0,1,0,0] but most of the time it is easier to just work with lists as shown in my answer. Aug 16, 2013 at 23:18
• @ Mr.Wizard. Thank You! I have been studying the code and I have two questions. Why is the first argument {s} passed in wrapped in a List? Also do I have this right, The function will only execute with condition Length[List[s]] == Length[r]? Aug 19, 2013 at 4:17

Your basic (simple, but inefficient) method is to use ReplaceRepeated:

start =
{{0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0}};

start //. {a___, 0, 0, 1, 0, 0, b___} :> {a, .5, .5, 1, .5, .5, b}

{{0.5, 0.5, 1, 0.5, 0.5, 1, 0, 1, 1, 0.5, 0.5, 1, 0.5, 0.5},
{0, 0, 0.5, 0.5, 1, 0.5, 0.5, 0.5, 0.5, 1, 0.5, 0.5, 0, 0}}


Your next level of optimization is to find all the positions first, and then replace.
I'll use a nice ReplaceList method from Jan Pöschko for the sequence position step.

f[{s__}, r_List][v_List] /; Length[{s}] == Length[r] :=
Module[{m = v, n = Length[{s}]},
m[[# + 1 ;; # + n]] = r; & /@
ReplaceList[v, {a___, s, ___} :> Length[{a}]];
m
]

p1 = {0, 0, 1, 0, 0};
p2 = {.5, .5, 1, .5, .5};

f[p1, p2] /@ start

{{0.5, 0.5, 1, 0.5, 0.5, 1, 0, 1, 1, 0.5, 0.5, 1, 0.5, 0.5},
{0, 0, 0.5, 0.5, 1, 0.5, 0.5, 0.5, 0.5, 1, 0.5, 0.5, 0, 0}}


For ultimate optimization you would use a faster sequence position function such as seqposCB from Leonid Shifrin posted in position of sequence of elements in list.

For a literal pattern as in this example the function SequencePosition introduced in 10.1.0 provides a much faster method than ReplaceList shown above.

f2[s_List, r_List][v_List] /; Length[s] == Length[r] :=
Module[
{m = v, n = Length[s]}, m[[# ;; #2]] = r; & @@@ SequencePosition[v, s];
m
]

rand = RandomInteger[1, 50000];
AbsoluteTiming[r1 = f[p1, p2][rand];]  // First
AbsoluteTiming[r2 = f2[p1, p2][rand];] // First
r1 === r2

0.551052

0.00407597

True


Using sequenceReplace defined here, you can do It as:

list = {{0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0}}
sequenceReplace[#, {0,0,1,0,0}:> Sequence@@{.5, .5, 1, .5, .5}]&/@list


Since I don't have SequencePosition:

ReplaceSequence[list_, fr_, to_] :=
With[{le = Length@fr},
ReplacePart[
list,
Dispatch[
Rule @@@
Level[
Map[Transpose[{#, to}] &,
Map[Range[#, # + le - 1] &,
Flatten@Position[Partition[list, le, 1], f]]],
{2}]
]]]

ReplaceSequence[RandomInteger[1, 50000], fr, to]; //
AbsoluteTiming // First

0.070000

list =
{{0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0}};

p1 = {0, 0, 1, 0, 0};
p2 = {.5, .5, 1, .5, .5};


Since V 11.3 there is SequenceReplace and since V 12.1 Splice

SequenceReplace[#, p1 :> Splice @ p2] & /@ list


gives the expected result:

{{0.5, 0.5, 1, 0.5, 0.5, 1, 0, 1, 1, 0.5, 0.5, 1, 0.5, 0.5},
{0, 0, 0.5, 0.5, 1, 0.5, 0.5, 0.5, 0.5, 1, 0.5, 0.5, 0, 0}}