Re: FixedPoint and SameTest
- To: mathgroup@smc.vnet.net
- Subject: [mg11792] Re: FixedPoint and SameTest
- From: Paul Abbott <paul@physics.uwa.edu.au>
- Date: Sat, 28 Mar 1998 00:25:27 -0500
- Organization: University of Western Australia
- References: <6fd3si$687@smc.vnet.net>
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
____________________________________________________________________