@*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 ky_1\le y_2$, and we choose that one. It's easy to check that the triples chosen in this way are commafree. Similar constructions are possible when $n=5$ or $n=7$. But the case $n=9$ already gets a bit dicey, and when $n$ is really large it's not at all clear that commafreeness is possible. Eastman's paper resolved a conjecture made by Golomb, Gordon, and Welch in their pioneering paper about comma-free codes (1958). (Of course, it's not at all clear that we would want to actually {\it use\/} a commafree code when $n$ is large; but that's another story, and beside the point. The point is that Eastman discovered a really interesting algorithm.) @d maxn 105 @c #include #include int x[maxn+maxn+maxn]; int b[maxn+maxn+maxn]; int bb[maxn]; @; main (int argc,char*argv[]) { register int i,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;j0$for every boundary marker~$b_j$. However, we won't need to use that fact explicitly.) The algorithm can be described with terminology based on the topography of Nevada: Say that$i$is a {\it basin\/} if the subwords satisfy$y_{i-1}>y_i\le y_{i+1}$. There must be at least one basin; otherwise all the$y_j$would be equal, and$x$would equal one of its cyclic shifts. We look at consecutive basins,$i$and~$j$; this means that$iy_{k+1}$. (For example, suppose$i=2$and$j=9$are consecutive basins. Then we have$y_1>y_2\le y_3\le\cdots\le y_q>y_{q+1}>\cdots>y_9\le y_{10}$, for some range element$2= @; for (p=1,t=n;t>1;t=tt,p++) @; @ @= for (j=n;j= int compare(register int i) { register int j; if (b[i]-b[i-1]==b[i+1]-b[i]) { for (j=0;b[i]+jx[b[i]+j]); } return 0; /* $y_{i-1}=y_i$ */ } return (b[i]-b[i-1]>b[i+1]-b[i]); } @ @= { for (tt=0,i=1;i<=t;i++) if (compare(i)) break; if (i>t) { fprintf(stderr,"The input is cyclic!\n"); exit(-666); } for (;compare(i+1);i++) ; /* advance to the first basin */ for(;i<=t;i=j) { for (q=i+1;compare(q+1)==0;q++) ; /* climb the range */ for (j=q+1;compare(j+1);j++) ; /* advance to the next basin */ if ((j-i)&1) @; } printf("Phase %d leaves",p); for (k=0;k= { if ((q-i)&1) q++; if (q0;k--) bb[k]=bb[k-1]; bb[0]=b[q-t]; } } @*Index.