Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
1  
Related: Finding a subsequence in a list –  ssch Dec 8 '13 at 15:33
add comment

9 Answers

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.

share|improve this answer
add comment

One pattern solution is simply

list //. {s___, 0, -1, e___} :> {s, 1, -1, e}
share|improve this answer
add comment

This should be pretty fast:

list - (list + 1) Join[Rest[list], {0}]
share|improve this answer
    
+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
add comment

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

list = RandomInteger[{-1, 0}, 5]
Clear[f];
f[{0, -1}] := 1
f[{x_, _}] := x
Developer`PartitionMap[f, list, 2, 1, 1, 0]
(* {0, 0, -1, 0, -1} *)
(* {0, 1, -1, 1, -1} *)
share|improve this answer
    
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 Developer`PartitionMap 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
add comment

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

toLinkedList[l_List] := Fold[{#2, #1} &, {}, Reverse@l]
replRec[l_List] := replRec[toLinkedList[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.

share|improve this answer
1  
+1. It crossed my mind to try it here, but I didn't have the time. –  Leonid Shifrin Dec 9 '13 at 11:15
add comment

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}
share|improve this answer
add comment

This is just another approach:

f[0] = 1; f[-1] = -1;
MapAt[f, list, Position[Rest[list], -1, {1}]]
share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.