# 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?

-
Related: Finding a subsequence in a list – ssch Dec 8 '13 at 15:33

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][[2]]
(* {1, -1, 0, 1, -1} *)

f[{n_, _}] := n;
f[{0, -1}] := 1;
CellularAutomaton[{f[#]&, {}, {{0}, {1}}}, list, 1][[2]]
(* {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 – Coolwater Dec 8 '13 at 19:09
@Coolwater, Join is a tiny bit faster for me. – Simon Woods Dec 8 '13 at 19:18
+1, a bit faster then my UnitStep. – ybeltukov Dec 9 '13 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 – Mr.Wizard Dec 9 '13 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. – rcollyer Dec 9 '13 at 14:46
I like it too. – Mr.Wizard Dec 9 '13 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. – Leonid Shifrin Dec 9 '13 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[0] := (Sow[g[0]]; g[0] = 0;);
f[-1] := ((g[0] = 1); Sow[-1])

g[0] = Sow[0]; (*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[0] = 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[1];
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.

-