Re: Re: FixedPoint and SameTest
- To: mathgroup@smc.vnet.net
- Subject: [mg11817] Re: [mg11792] Re: FixedPoint and SameTest
- From: "Jürgen Tischer" <jtischer@pitagoras.univalle.edu.co>
- Date: Tue, 31 Mar 1998 02:28:35 -0500
Hi Paul,
I couldn't make it nicer (I still would like to know if one can access
inside of FixedPointList the list while being built up), but at least
my version runs a lot faster.
CycleList[f_, x0_] :=
Module[{g},
With[{li= FixedPointList[(g[#]=f[#]) &
,x0,SameTest->(ValueQ[g[#2]]&)]},
Split[li,#2!=Last[li]&]]]
I checked it with
f[x_,n_]:=Mod[x+1,n];x0=0;
For my PC (Intel 200 pro, 64M Ram) it took 3 seconds to finish for
n=5000, as opposed to 28 seconds with the definition of Marko Petkovsek
and Tomaz Pisanski.
J|rgen
-----Original Message-----
From: Paul Abbott <paul@physics.uwa.edu.au> To: mathgroup@smc.vnet.net
Subject: [mg11817] [mg11792] Re: FixedPoint and SameTest
>richard j. gaylord wrote:
>
>> i recieved the following question and thought i'd post an answer here
>> for others who might want to do the same sort of thing.
>>
>> > What is a simple procedure that works like NestList but stops
>> >once an element in the list repeats.
>> >
>> >I want something like FixedPointList, except that instead of stopping
>> >when two consecutive outputs are the same, it would stop when it
>> >generates an element it has generated earlier.
>>
>> here it is, shown for a simple example a function that picks a random
>> integer between 1 and (the last random integer generated + 4):
>>
>> In[39]:=
>> SeedRandom[88]
>> FixedPointList[Random[Integer, {1, # + 4}]&, 5 ]
>>
>> Out[40]=
>> {5,4,2,4,6,3,5,2,3,1,5,3,1,5,5}
>>
>> In[41]:=
>> SeedRandom[88]
>> lis = {};
>> FixedPointList[(AppendTo[lis, #]; Random[Integer, {1, # + 4}] )&, 5,
>> SameTest -> (MemberQ[lis, #2] == MemberQ[lis,
>> #1] &) ]
>>
>> Out[43]=
>> {5,4,2,4}
>>
>> well, la di da [as anne hall would have said]
>
>In the Mathematica Journal 6(4): 24-26, Marko Petkovsek and Tomaz
>Pisanski introduce a CycleList function:
>
>A function may not have fixed points, however, or they may not be
>reachable from the given starting value. In general, even if the
>sequence x\_0, f(x\_0), f(f(x\_0)), ... contains only finitely many
>different values, it may happen that none of them is a fixed point. In
>that case, however, sooner or later one value is bound to repeat, and
>so a cycle is reached and then followed forever.
>
>To find a cycle of f, we use FixedPoint applied not to f itself but to a
>function that takes a list as argument:
>
> AppendTest[f_, l_List] :=
> If[MemberQ[Drop[l, -1], Last[l]], l, Append[l, f[Last[l]]]]
>
>AppendTest[f,l] applies f to the last element of the list l (say, y),
>and appends the value f(y) to l provided that y does not appear
>elsewhere in l. The function Cycle returns the cycle of f reached from
>x\_0. The related function CycleList returns a list of two lists, the
>first containing the initial tail and the second the cycle of f reached
>from x\_0:
>
> CycleList[f_, x0_] :=
> Module[{l, n}, l = FixedPoint[AppendTest[f, #1] & , {x0}];
> n = First[First[Position[l, Last[l]]]];
> SplitList[Drop[l, -1], n - 1]]
>
> Cycle[f_, x0_] := Last[CycleList[f, x0]]
>
>The function SplitList simply breaks a list into two parts after the
>n-th element:
>
> SplitList[l_, n_] := {Take[l, n], Drop[l, n]}
>
>(Note that the functionality of SplitList is different from the new
>built-in function Split.)
>
>For Richard's example,
>
> SeedRandom[88]
> CycleList[Random[Integer, {1, #1 + 4}] & , 5]
> {{5},{4,2}}
>
>Cheers,
> Paul
>
>____________________________________________________________________
>Paul Abbott Phone: +61-8-9380-2734
>Department of Physics Fax: +61-8-9380-1014
>The University of Western Australia Nedlands WA 6907
>mailto:paul@physics.uwa.edu.au AUSTRALIA
>http://www.pd.uwa.edu.au/~paul
>
> God IS a weakly left-handed dice player
>____________________________________________________________________
>