# How to replace an element in a list based on the value of the next element?

I use Mathematica a little bit. I try to understand it, but it is hard

I have a list of 5 numbers selected randomly from 0 and -1. I have to replace a 0 with a 1 when the 0 is followed by -1.

My wrong solution is:

list = RandomInteger[{-1, 0}, 5]
(* {0, 0, 0, -1, 0} *)

list /. x_ /; x == 0 -> 1
(* {1, 1, 1, -1, 1} *)


I need get: {0, 0, 1, -1, 0}. How do I manipulate a list to change the previous element if the next element is -1?

One of the possible solutions:

list = RandomInteger[{-1, 0}, 5]
(* {0, -1, 0, 0, -1} *)

list2 = list + Append[UnitStep[-1 - Differences[list]], 0]
(* {1, -1, 0, 1, -1} *)


Another two are

Partition[list, 2, 1, 1, 0] /. {{0, -1} -> 1, {n_, _} :> n}
(* {1, -1, 0, 1, -1} *)

f[_, n_] := n;
f[-1, 0] := 1;
Reverse@FoldList[f, list[[-1]], Rest@Reverse@list]
(* {1, -1, 0, 1, -1} *)


The first solution is very fast for big lists. It takes $0.08$ s for a list with $1\,000\,000$ elements. The second and the third one take $0.8$ s. Halirutan's ReplaceAll will take several hours because it has $O(n^2)$ complexity.

Update

One can use cellular automata:

CellularAutomaton[{{_, 0, -1} -> 1, {_, n_, _} :> n}, list, 1][]
(* {1, -1, 0, 1, -1} *)

f[{n_, _}] := n;
f[{0, -1}] := 1;
CellularAutomaton[{f[#]&, {}, {{0}, {1}}}, list, 1][]
(* {1, -1, 0, 1, -1} *)


It is not very fast ($1.8$ s for $1\,000\,000$ elements) but it shows wide opportunities of Mathematica.

One pattern solution is simply

list //. {s___, 0, -1, e___} :> {s, 1, -1, e}


This should be pretty fast:

list - (list + 1) Join[Rest[list], {0}]

• +1, neat one, Append is faster though Dec 8, 2013 at 19:09
• @Coolwater, Join is a tiny bit faster for me. Dec 8, 2013 at 19:18
• +1, a bit faster then my UnitStep. Dec 9, 2013 at 0:08

Since no one has suggested it, there is also DeveloperPartitionMap which maps a function across a partitioned list:

list = RandomInteger[{-1, 0}, 5]
Clear[f];
f[{0, -1}] := 1
f[{x_, _}] := x
DeveloperPartitionMap[f, list, 2, 1, 1, 0]
(* {0, 0, -1, 0, -1} *)
(* {0, 1, -1, 1, -1} *)

• Not as fast as the pure numeric methods but far more general. +1 Dec 9, 2013 at 8:07
• @Mr.Wizard I like DeveloperPartitionMap because of its relative compactness and simplicity. While not a speed demon, I think the other factors make it a nice contender. Dec 9, 2013 at 14:46
• I like it too. Dec 9, 2013 at 18:16

I implemented a solution based on linked lists, discussed by Leonid Shifrin here.

toLinkedList[l_List] := Fold[{#2, #1} &, {}, Reverse@l]
replRec[{0, tail : {-1, _List}}, res_] := replRec[tail, {1, res}]
replRec[{int_Integer, tail_List}, res_] := replRec[tail, {int, res}]
replRec[{}, res_] := Reverse[Flatten[res]]


For example

replRec[{0, 0, 0, -1, 0}]
(* Out: {0, 0, 1, -1, 0} *)


I tried this on a list of the size of 10^6, which required me to change the iteration limit:

Block[{\$IterationLimit = 10^7}, replRec[list]] // AbsoluteTiming


It took 1.34 seconds, compared to 0.39 with Michael E2's Replace method.

• +1. It crossed my mind to try it here, but I didn't have the time. Dec 9, 2013 at 11:15

Not so fast but faster than replacement rules and fun. We are going to scan on reversed list and each -1 or 0 will change the value of Sown element.

list = RandomInteger[{-1, 0}, 10]

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

f := (Sow[g]; g = 0;);
f[-1] := ((g = 1); Sow[-1])

g = Sow; (*default value*)

Reap[Scan[f, Reverse@list]][[2, 1]] // Reverse

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


This is just another approach:

f = 1; f[-1] = -1;
MapAt[f, list, Position[Rest[list], -1, {1}]]


a basic solution :

    list = RandomInteger[{-1, 0}, 5]
(* {0, -1, 0, 0, -1} *)

Append[
Table[If[list[[i + 1]] === -1, 1, list[[i]]], {i, Length[list] - 1}],
Last[list]]


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

It is fast.

A general way with patterns, that is pretty efficient and of linear complexity. (@halirutan's is also easily adapted to general patterns). Here pat should be of the form {pat1, lookahead} -> replacement):

seqRep[list_, pat_] :=
(Replace[Partition[list, 2, 1], {pat, {x_, y_} :> x}, {1}]) ~Append~ Last[list]


Example:

SeedRandom;
list = RandomInteger[{-1, 0}, 10]
(* {0, 0, -1, 0, -1, -1, -1, 0, -1, 0} *)

seqRep[list, {0, -1} -> 1]
(* {0, 1, -1, 1, -1, -1, -1, 1, -1, 0} *)


A fast way, that like others works on the OP's example of a list of integers. Its speed comes from auto-parallelization:

cf = Compile[{{x, _Integer}, {y, _Integer}},
If[x == 0 && y == -1, 1, x],
RuntimeAttributes -> {Listable}, Parallelization -> True,
RuntimeOptions -> "Speed", CompilationTarget -> "C"
]


Usage:

cf[Most@list, Rest@list]~Append~Last[list]
(* {0, 1, -1, 1, -1, -1, -1, 1, -1, 0} *)


As far as speed, on a list of 10^6 integers, the Replace method took 0.42 sec., the compiled method took 0.051 sec., @ybeltukov's UnitStep` method took 0.071 sec., and Simon Wood's method took 0.071 sec.