\datethis \everypar{\looseness=-1} @*Intro. This program is an iterative implementation of an interesting recursive algorithm due to Willard~L. Eastman, {\sl IEEE Trans.\ \bf IT-11} (1965), 263--267: Given a sequence of nonnegative integers $x=x_0x_1\ldots x_{n-1}$ of odd length~$n$, where $x$ is not equal to any of its cyclic shifts $x_k\ldots x_{n-1}x_0\ldots x_{k-1}$ for \$1\le k #include int x[maxn+maxn]; int b[maxn+maxn]; int bb[maxn]; @; main (int argc,char*argv[]) { register int i,i0,j,k,n,p,q,t,tt; @; @; @; } @ @= if (argc<4) { fprintf(stderr,"Usage: %s x1 x2 ... xn\n",argv[0]); exit(-1); } n=argc-1; if ((n&1)==0) { fprintf(stderr,"The number of items, n, should be odd, not %d!\n",n); exit(-2); } for (j=1;j= @; for (p=1,t=n;t>1;t=tt,p++) @; @ We might need to refer to |b[n+n-1]|, but not |b[n+n]|. @= for (j=n;j= int less(register int i) { register int j; if (b[i]-b[i-1]==b[i+1]-b[i]) { for (j=0;b[i]+j= { for (i=1;;i++) if (!less(i)) break; /* now |i<=t| and |y[i-1]>=y[i]| */ for (i+=2;i<=t+2;i++) if (less(i-1)) break; if (i>t+2) { fprintf(stderr,"The input is cyclic!\n"); exit(-666); } /* now |y[i-3]>=y[i-2]; } printf("Phase %d leaves",p); for (k=0;k=t| at this point, we have wrapped around,'' so we actually want to retain the boundary point |i-t|. (This case will arise at most once per phase, because |j>=i+3| and we must have |j=i0+t|. Therefore |i-t| will be smaller than all of the previously retained points, and we want to shift them one space to the right.) @= { if (i0;k--) bb[k]=bb[k-1]; bb[0]=b[i-t]; } } @ @= for (j=b[0];j