Cliff Bergman on Tue, 31 Dec 2002 09:49:35 -0600 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: How to find the period in a vector ? |
The other way, which is probably more practical if you already have the vector in memory is to use Gusfield's Z function. This is from his book: D. Gusfield, {\it Algorithms on strings, trees, and sequences}, Cambridge Univ. Press, Cambridge, 1997; MR 99b:68095.
I once coded the algorithm to do this in Gap. (My apologies to this list. This was before I was aware of pari.) I'm including the code below, in case you know gap well enough to read it. One wrinkle in the code: in order to account for a possible "tail" on the sequence before the periodic part, I first reverse the sequence and then compute the period.
I'd be glad to try and help explain this code if it is unreadable. --cliff b. # Compute a version of the 'Z' function discussed in Chapter 1 of # Gusfield's book. The only difference is that we are comparing to the # _end_ of the string, rather than the beginning. Thus, given a string # s, z[k] is the number of characters ending with s[k] that matches a # suffix of s. ExplicitCompare:=function(s,a,b) # Returns the number of characters of s, ending at positions a and b # that agree. Uses brute force. local i,min; i:=0; min:=Minimum(a,b); while (i< min and s[a-i]=s[b-i]) do i:=i+1; od; return i; end; SuffixMatch:=function(s) # Returns the z function described above. local n,z,i,r,l,k,kk,beta; n:=Length(s); z:=[1..n-1]*0; #Basis for the recursive definition: compute z[n-1] explicitly. i:=ExplicitCompare(s,n-1,n); z[n-1]:=i; if i>0 then r:=n-1; l:=n-i; else r:=n; l:=n; fi; # Now, Compute z[k] by working downward to 1 for k in [n-2,n-3..1] do if k<l then # Determine z[k] by explicit comparison i:=ExplicitCompare(s,k,n); z[k]:=i; if i>0 then r:=k; l:=k-i+1; fi; else # if k>=l kk:=n-r+k; beta:= k-l+1; if z[kk] < beta then z[k]:=z[kk]; else i:=ExplicitCompare(s,l-1,n-beta); z[k]:=beta+i; l:=l-i; r:=k; fi; # if kk<beta fi; # if k<l od; return z; end; # Accepts a finite string as input, and determines whether it is # eventually periodic. If so, we return the length of the period and the # length of the tail. If not, return 0 for the period. period:=function(s) local z, p,t,k, n, kmax; # Find the location of the largest z-value z:=SuffixMatch(s); n:=Length(s); kmax:=n-1; for k in [n-2,n-3..1] do if z[k]>z[kmax] then kmax:=k; fi; od; p:=n-kmax; #period t:=n-p-z[kmax]; #tail # Heuristics to determine whether the string should be considered # eventually periodic. Change to suit yourself. if z[kmax]>p or 3*z[kmax]>t+p then return [p,t]; else return [0,n]; fi; end;--On Sunday, December 15, 2002 12:12:11 PM +0100 Thomas Baruchel <thomas.baruchel@libertysurf.fr> wrote:
Brest, le dimanche 15 décembre Hi, I wonder what is the best way to find the length of the period in a vector. I suppose the vector is completely periodical, eg: [1,2,3,1,2,3,1,2,3], though I'm not sure that the length of the vector is divisible by the length of the period, eg: [1,2,3,1,2,3,1,2] (without the last '3'). Is there something quick enough to do with GP ? -- Deux choses remplissent le coeur d'une admiration et d'une vénération toujours nouvelles et toujours croissantes, à mesure que la réflexion s'y attache et s'y applique : le ciel étoilé au-dessus de moi et la loi morale en moi. (Emmanuel Kant)
Cliff Bergman Department of Mathematics Iowa State University Ames, Iowa 50011