Re: How to find the period in a vector ?

[Cliff Bergman <cbergman@iastate.edu>]

I know of two ways to find the period of a vector. One way is to use 
Floyd's algorithm. It is described in Exercise 6, page 7 of Volume 2 of the 
Art of Computer Programming by Don Knuth. (There is also an enhanced 
version of the algorithm due to, I think, Lamport. I can't find the 
reference at the moment.)

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