10
$\begingroup$

I am using Mathematica to run a probabilistic simulation. Essentially, I have a list of members of a population (they only have one, numerical, attribute, so it's just implemented as a list of numbers), and a function to move from one generation to the next, in a random manner.

I need to iterate this function on my list until the list exceeds a given length, and then I want the number of iterations/generations is took to reach that length. My first instinct would be to use a While loop, but I know that using explicit loops in Mathematica is usually bad practice. Unfortunately, I haven't been able to find a better or more functional construction, and that's where I'm asking for help.

$\endgroup$
1
  • 1
    $\begingroup$ without an example it's hard to say, but maybe NestWhile will be useful $\endgroup$
    – acl
    Oct 15, 2012 at 22:29

4 Answers 4

12
$\begingroup$

Very vague question but let me give you a start. Say you have a list l and a step function which appends or does not append a random element to your list. Now you want to call step over and over again, until your list reached a specific length:

step[{l_, iter_}] := 
  {If[RandomChoice[{True, False}], Append[l, RandomInteger[]], l], iter + 1}

Depending on the choice this returns an augmented list or the original list and (always) iter+1. Now you can use NestWhile and iterate as long as the Length of the First element is smaller than say 30

NestWhile[step, {{1, 2, 3}, 0}, Length[First[#]] < 30 &]

(*
  {{1, 2, 3, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 
  1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0}, 45}
*)

You get back your final generations and the number of iterations it took.

$\endgroup$
3
  • $\begingroup$ Sorry if I was being vague- I wasn't sure if I should include explicit code. In any case, NestWhile is exactly what I wanted. $\endgroup$ Oct 16, 2012 at 1:48
  • 2
    $\begingroup$ @CalvinMcPhail-Snyder Including code always helps. $\endgroup$ Oct 16, 2012 at 4:07
  • $\begingroup$ @CalvinMcPhail-Snyder It's not that we need code to give answers even to vague questions, but since we don't know your data-structures, memory- and time-restrictions it's hard to give good advice. Especially, read MrWiz answer if you have several ten-thousand elements in your list and run into time issues. $\endgroup$
    – halirutan
    Oct 16, 2012 at 8:01
10
$\begingroup$

I know halirutan's answer is intended only as a simple example but I believe it is worth noting that it is inefficient for the specific operation that he illustrates.

One could directly write RandomInteger[1, 30] but that has no "loop" condition and is therefore inapplicable. What I show below may also be inapplicable, but hopefully it is still of interest.

The inefficiency in step is the use of Append to collect results, a method which becomes very slow on long lists due to reallocation. The most general efficient method is Sow and Reap. For example:

step2[n_] := If[RandomInteger[] === 1, Sow @ RandomInteger[]; n + 1, n]

Reap[NestWhile[step2, 0, # < 20 &]][[2, 1]]
{1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1}

Timing compared to the original:

NestWhile[step, {{}, 0}, Length[First[#]] < 50000 &] // AbsoluteTiming // First

Reap[NestWhile[step2, 0, # < 50000 &]][[2, 1]] // AbsoluteTiming // First

3.4944061

0.1248003

The timing difference is less with short lists and greater with long ones due to different computational complexity.

You may have noticed that my method does not return the number of loops completed as does haliruten's. I left this out for simplicity but it could be achieved like this at the cost of some memory:

Reap[Length@NestWhileList[step2, 0, # < 20 &]]
{47, {{0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1}}}

Or without more memory but slightly more time and code:

step3[{iter_, n_}] :=
  {iter + 1, If[RandomInteger[] === 1, Sow @ RandomInteger[]; n + 1, n]}

Reap[First @ NestWhile[step3, {0, 0}, Last@# < 20 &]]
{35, {{1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1}}}

Or with explicit iterator variables:

step4[___] := (j++; If[RandomInteger[] === 1, i++; RandomInteger[], ## &[]])

Block[{i = 0, j = 0},
 {NestWhileList[step4, 0, i < 20 &], j}
]
{{0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1}, 45}
$\endgroup$
7
$\begingroup$

OK, so you have a function which takes a list (your current generation) and returns a list (your next generation), and a list representing your initial generation, and you want to iterate until the length of the list representing the current generation is larger than some value. In other words, the While solution you thought of looks something like this:

growthTime[nextGenerationFunction_, initialGeneration_, size_] :=
  Module[{count = 0, generation = initialGeneration},
    While[Length@generation < size,
      generation = nextGenerationFunction@generation;
      count++];
   count]

OK, let's functionalize it. There are several ways to do this.

The NestWhile way

One obvious way to transform a While loop to functional form is to use NestWhile provided by Mathematica. Basically, the body of the While is a function which maps the state before execution to the state after execution. What we have to do is to make this function explicit by removing the (relative to the while loop global, but relative to the function local) state.

First, note that the loop updates two things: The list representing the current generation, and the count of iterations. Let's as first step put them both in a list, so we only have with a single item which we then later can return. The while loop body now consists of a single assignment:

growthTime[nextGenerationFunction_, initialGeneration_, size_] :=
  Module[{countAndGeneration = {0, initialGeneration}},
    While[Length@Last@countAndGeneration < size,
      countAndGeneration =
        {First@countAndGeneration + 1,
         nextGenerationFunction@Last@countAndGeneration}];
   First@countAndGeneration]

In the next step, we turn the update into an actual function, and the same with the condition; also we drag the First out of the Module:

growthTime[nextGenerationFunction_, initialGeneration_, size_] :=
  First@Module[{countAndGeneration = {0, initialGeneration}},
    While[(Length@Last@# < size&)[countAndGeneration],
      countAndGeneration =
        ({First@# + 1, nextGenerationFunction@Last@#}&)@countAndGeneration];
   countAndGeneration]

Now we have the right structure to directly transform

Module[{variable = init},
  While[condition[variable], variable = update[variable]];
  variable]

into

NestWhile[update, init, condition]

and get

growthTime[nextGenerationFunction_, initialGeneration_, size_] :=
  First@NestWhile[{First@# + 1, nextGenerationFunction@Last@#}&,
                  initialGeneration,
                  Length@Last@# < size&]

The recursive way

The recursive solution is based on the simple observation that the number of iterations you need to reach the length is 0 if your initial generation already has the required length, and one more than the number needed if you started with the second generation. This quite directly leads to the following definitions:

growthTime[nextGenerationFunction_, initialGeneration_, size_] /;
  Length@initialGeneration >= size := 0
growthTime[nextGenerationFunction_, initialGeneration_, size_] :=
  1 + growthTime[nextGenerationFunction,
                 nextGenerationFunction@initialGeneration,
                 size]

or if you prefer it in a single definition:

growthTime[nextGenerationFunction_, initialGeneration_, size_] :=
  If[Length@initialGeneration >= size,
     0,
     1 + growthTime[nextGenerationFunction,
                    nextGenerationFunction@initialGeneration,
                    size]]
$\endgroup$
4
$\begingroup$

My first answer explored a specific use of NestWhile in an effort to make it more efficient. This answer will explore other alternatives to While loops.

Here is a simple example of While used to find the GCD of two numbers:

whileGCD = 
  Module[{a = #, b = #2},
    While[b != 0, {a, b} = {b, Mod[a, b]}];
    a
  ] &;

whileGCD[96, 86]
2

A natural alternative for this is recursion. Here are a couple of ways to implement that:

gcd[a_, 0] = a;
gcd[a_, b_] := gcd[b, a ~Mod~ b]

gcd[96, 86]
2
If[#2 == 0, #, #0[#2, # ~Mod~ #2]] &[96, 86]
2

It is also possible to use ReplaceRepeated:

{96, 86} //. {{a_, 0} :> a, {a_, b_} :> {b, a ~Mod~ b}}
2

Note that none of these methods required Module to localize variables. This is a common theme when translating code from explicit loops to "functional iteration."

$\endgroup$

Your Answer

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

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