\datethis
@*Intro. This program finds the prime implicants of a given
self-dual threshold function. It outputs them in a format that
can be used as input to Mathematica to find ``optimum'' weights.

Input weights appear on the command line. They should sum to
an odd number; they specify the majority, with those multiplicities.
For example,
the arguments \.{13} \.{11} \.{7} \.{5} \.{3} \.{2} means
that the threshold function is ``majority of
$\{13\cdot x_1,\;
11\cdot x_2,\;
7\cdot x_3,\;
5\cdot x_4,\;
3\cdot x_5,\;
2\cdot x_6\}$.''

@c
#include <stdio.h>
int w[1000];
int x[27]; /* 1 if in current implicant */
int s[27]; /* $s[l]=x[0]w[0]+\cdots+x[l-1]w[l-1]$ */
int a[27]; /* $a[l]=w[l]+\cdots+w[n-1]$ */
int going; /* have we printed any constraints yet? */

main(int argc, char *argv[])
{
  register int j,l,n,t;
  @<Read the command line@>;
  @<Print the first line of output@>;
  @<Backtrack through all prime implicants@>;
  @<Print the last line of output@>;
}

@ @<Read the command line@>=
n=argc-1;
if (n==0) {
  fprintf(stderr,"Usage: %s w1 w2...\n",argv[0]);
  exit(-1);
}
if (n>26) {
  fprintf(stderr,"Sorry, n (%d) must be at most 26!\n",n);
  exit(-9);
}
for (j=0;j<n;j++) {
  if (sscanf(argv[j+1],"%d",&w[j])!=1) {
    fprintf(stderr,"Bad weight (%s)!\n",argv[j+1]);
    exit(-2);
  }
  if (w[j]<=0) {
    fprintf(stderr,"Non-positive weight (%s)!\n",argv[j+1]);
    exit(-3);
  }
}
for (j=n-1,t=0;j>=0;j--) t+=w[j], a[j]=t;
if ((t&1)==0) {
  fprintf(stderr,"Total weight (%d) should be odd!\n",t);
  exit(-4);
}
t=(t+1)>>1;

@ @<Backtrack through all prime implicants@>=
l=0;
newlevel: x[l]=1, s[l+1]=s[l]+w[l];
if (s[l+1]>=t) {
  @<Print a linear constraint for the current prime implicant@>@;
  goto downsize;
}@+else {
  l++;
  goto newlevel;
}
downsize: x[l]=0;
if (s[l]+a[l+1]<t) goto backtrack;
s[l+1]=s[l];
l++;
goto newlevel;
backtrack:@+if (l) {
  l--;
  if (x[l]) goto downsize;
  goto backtrack;
}

@ @<Print the first line of output@>=
printf("(* optimizing the threshold function");
for (j=0;j<n;j++) printf(" %d",w[j]);
printf(" *)\n\nMinimize[{");
for (j=0;j<n;j++) printf("%s%c",j?"+":"",'a'+j);
printf(",\n ");

@ @<Print a linear constraint for the current prime implicant@>=
if (!going) going=1;
else printf("\n  && ");
for (j=0;j<n;j++) printf("%c%c",x[j]?'+':'-','a'+j);
printf(">=1");

@ @<Print the last line of output@>=
printf("},\n ");
for (j=0;j<n;j++) printf("%c%c",j?',':'{','a'+j);
printf("}]\n");

@*Index.