19
$\begingroup$

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?

Improve this question
$\endgroup$
1

9 Answers 9

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
12
$\begingroup$

One pattern solution is simply

list //. {s___, 0, -1, e___} :> {s, 1, -1, e}
Improve this answer
$\endgroup$
0
11
$\begingroup$

This should be pretty fast:

list - (list + 1) Join[Rest[list], {0}]
Improve this answer
$\endgroup$
3
  • $\begingroup$ +1, neat one, Append is faster though $\endgroup$
    – Coolwater
    Dec 8, 2013 at 19:09
  • $\begingroup$ @Coolwater, Join is a tiny bit faster for me. $\endgroup$
    – Simon Woods
    Dec 8, 2013 at 19:18
  • $\begingroup$ +1, a bit faster then my UnitStep. $\endgroup$
    – ybeltukov
    Dec 9, 2013 at 0:08
10
$\begingroup$

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} *)
Improve this answer
$\endgroup$
3
  • $\begingroup$ Not as fast as the pure numeric methods but far more general. +1 $\endgroup$
    – Mr.Wizard
    Dec 9, 2013 at 8:07
  • $\begingroup$ @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. $\endgroup$
    – rcollyer
    Dec 9, 2013 at 14:46
  • $\begingroup$ I like it too. $\endgroup$
    – Mr.Wizard
    Dec 9, 2013 at 18:16
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ +1. It crossed my mind to try it here, but I didn't have the time. $\endgroup$
    – Leonid Shifrin
    Dec 9, 2013 at 11:15
4
$\begingroup$

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}
Improve this answer
$\endgroup$
4
$\begingroup$

This is just another approach:

f[0] = 1; f[-1] = -1;
MapAt[f, list, Position[Rest[list], -1, {1}]]
Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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