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?

$\endgroup$
1
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.

$\endgroup$
12
$\begingroup$

One pattern solution is simply

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

This should be pretty fast:

list - (list + 1) Join[Rest[list], {0}]
$\endgroup$
3
  • $\begingroup$ +1, neat one, Append is faster though $\endgroup$
    – Coolwater
    Dec 8 '13 at 19:09
  • $\begingroup$ @Coolwater, Join is a tiny bit faster for me. $\endgroup$ Dec 8 '13 at 19:18
  • $\begingroup$ +1, a bit faster then my UnitStep. $\endgroup$
    – ybeltukov
    Dec 9 '13 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} *)
$\endgroup$
3
  • $\begingroup$ Not as fast as the pure numeric methods but far more general. +1 $\endgroup$
    – Mr.Wizard
    Dec 9 '13 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 '13 at 14:46
  • $\begingroup$ I like it too. $\endgroup$
    – Mr.Wizard
    Dec 9 '13 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.

$\endgroup$
1
  • 1
    $\begingroup$ +1. It crossed my mind to try it here, but I didn't have the time. $\endgroup$ Dec 9 '13 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}
$\endgroup$
4
$\begingroup$

This is just another approach:

f[0] = 1; f[-1] = -1;
MapAt[f, list, Position[Rest[list], -1, {1}]]
$\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.

$\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.

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .