@*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]+j**x[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.
`