MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

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
____________________________________________________________________



  • Prev by Date: Re: vectors in polar coordinates
  • Next by Date: Re: Mathematica frustrations...
  • Prev by thread: Re: FixedPoint and SameTest
  • Next by thread: Re: Re: FixedPoint and SameTest