#include <stdio.h>

unsigned short A[9][9];
unsigned short B[9][9];
unsigned short C[9][9];
unsigned short P[40324][9];
unsigned short Q[40324][9];

// n = 4 has   58 commutative semigroups
// n = 5 has  325 commutative semigroups
// n = 6 has 2143 commutative semigroups
unsigned short store[20200][9][9]; // only good for n = 4 or 5
unsigned short used[20200]; // only good for n = 4 or 5
unsigned short distributes[20200]; // only good for n = 4 or 5
//
unsigned long id;
unsigned long n;
unsigned long nf_gbl;
unsigned long ki_gbl;
unsigned long ka;
unsigned long kc;

unsigned long isotest();
unsigned long astest();
unsigned long compare_A_B();
unsigned long compare_A_C();
unsigned long perm();

unsigned long maxcount;
unsigned long count;

/*================================================*/
int main( int argc, char **argv )
{
int i,j,k,l;
int valcnt;
unsigned long prev;
unsigned long w;
unsigned long x;
unsigned long y;
unsigned long sum;
unsigned long rslt1;
unsigned long rslt2;
unsigned long prod1;
unsigned long prod2;
unsigned long valtbl[9];

for (i=0;i<20200;i++)
{
  used[i] = 0;
  distributes[i] = 0;
}


if ( argc < 3 )
{
   printf("Usage: gensemi <n> <max-count>\n");  
   exit(1);
}

n = 5;
id = 0;
count = 0;

n = strtoul(argv[1],NULL,0);
maxcount = strtoul(argv[2],NULL,0);

for (k=1;k<=n;k++)
{
  for (l=1;l<=n;l++)
  {
    A[k][l] = 1;
  }
}
A[n][n] = 0;

nf_gbl = perm();

#undef DEBUG

i = n;
j = n;

nextatij:

A[i][j] = A[i][j] + 1;

if ( A[i][j] <= n )
  goto test;
//
//
// backtrack
//

A[i][j] = 0;

if (j == 1)
{
  j = n;  // last entry of previous row i-1
  i = i-1;
}
else
{
  j = j-1; // previous entry of current i-th row
}


if (i == 1 && j == 1 )
{
  printf("done\n");
  goto done;
}
goto nextatij;




test:
ka = astest();

if ( ka == 0 )
  goto nextatij;

#if 1
ki_gbl = isotest();
if ( ki_gbl == 0 )
  goto nextatij;
#endif

if ( i == n && j == n )
  goto gotone;

if ( j == n )
  goto label60; // goto first entry of next row i+1

j = j+1;   // go forward on same row i
goto nextatij;

label60: // goto first entry of next row i+1
j = 1;
i = i+1;
goto nextatij;



gotone:

id = id+1;

// check for commutative
for (k=1;k<=n;k++)
{
  for (l=1;l<=n;l++)
  {
	  if (A[k][l] != A[l][k])
	  {
         goto nextatij;
	  }
  }
}

count++;
if (count > maxcount )
   goto done;

//printf("OK n=%d id=%d count=%d\n",n,id,count);

for (k=1;k<=n;k++)
{
  for (l=1;l<=n;l++)
  {
    store[count-1][k][l] = A[k][l];
  }
}
//
// now test current one for distribute over previous
// ones
//
if ( count > 1 )
{

for (prev = 0;prev<(count-1);prev++)
{
 //make sure prev is additively idempotent
 for (x=1;x<=n;x++)
 {
   if (store[prev][x][x] != x )
   {
	 goto next_prev;
   }
   valtbl[x] = 0;
 }

 for (x=1; x<=n; x++)
 {
   for (y=1; y<=n; y++)
   {
     valtbl[ store[prev][x][y] ] = 1;
   }
 }

 for (x=1;x<=n;x++)
 {
   if ( valtbl[x] == 0 )
	   goto next_prev;
 }

 for (x=1; x<=n; x++)
 {
   valtbl[x] = 0;
 }

 for (x=1; x<=n; x++)
 {
   for (y=1; y<=n; y++)
   {
     valtbl[ A[x][y] ] = 1;
   }
 }

 valcnt = 0;
 for (x=1;x<=n;x++)
 {
   if ( valtbl[x] != 0 )
	 valcnt++;
 }
 if ( valcnt < (n-2) )
	 goto next_prev;



 for (w=1; w<=n; w++)
 {
   for (x=1; x<=n; x++)
   {
     for (y=1; y<=n; y++)
     {
       sum = store[prev][x][y];
       rslt1 = A[w][sum];
       prod1 = A[w][x];
       prod2 = A[w][y];
       rslt2 = store[prev][prod2][prod1];
       if ( rslt1 != rslt2 )
          goto not_distributive;
     } // y
   } // x
 } // w
distributive:
 printf("%4d is distributive over %4d prev\n",count,prev+1);
 used[count] = 2;
 distributes[count] = prev+1;
 used[prev+1] = 1;

not_distributive:

 next_prev:

} // prev

} // count > 1

goto nextatij;



done:

for (i=1;i < (count+1); i++ )
{
 if ( distributes[i] != 0 )
 {
   printf("\n\nOK %d distributes over %d\n",i,distributes[i]);
   for (k=1;k<=n;k++)
   {
     for (l=1;l<=n;l++)
     {
       printf("%2d ", store[i-1][k][l] );
     }
     printf("\n");
   }
 }
 else if ( used[i] != 0 )
 {
   printf("\n\nUSED: %d\n",i);
   for (k=1;k<=n;k++)
   {
     for (l=1;l<=n;l++)
     {
       printf("%2d ", store[i-1][k][l] );
     }
     printf("\n");
   }
 }
}
exit(1);

}


/*****************************************/


unsigned long isotest( void )
{
unsigned long i,j,k,l,na,ci,cj;

for (l=1;l<=nf_gbl;l++)
{
 for ( i=1;i<=n;i++)
 {
   for ( j=1; j <=n; j++)
   {
     ci = Q[l][i];
     cj = Q[l][j];

     na = A[ ci ][ cj ];

     if ( na == 0 )
       B[i][j] = 0;
	 else
       B[i][j] = P[l][na];
   }
 }

 kc = compare_A_B(); // compare(A,B,n,kc)
 if ( kc == 0 )
   return(0);   // equal

 for (i=1;i<=n;i++)
   for (j=1;j<=n;j++)
     C[i][j] = B[j][i];

 kc = compare_A_C(); // compare(A,C,n,kc)
 if ( kc == 0 )
   return(0);   // equal

} // for over l

return(1); // not equal
}


/*****************************************/


unsigned long astest()
{
unsigned long i,j,k,mf,ms;

ka = 1;

for (i=1;i<=n;i++)
{
  for (j=1;j<=n;j++)
  {

    mf = A[i][j];

    if ( mf == 0 )
       return(1);

    for (k=1;k<=n;k++)
    {
      ms = A[j][k];

      if ( ms == 0 )
         goto next_i;

      if ( A[i][ms] == 0 )
         continue;          // next k

      if ( A[mf][k] == 0 )
         continue;          // next k

      if ( A[i][ms] != A[mf][k] )
	  {
         ka = 0;
         return(0); // failed astest
	  }
    } // k
  } // j
next_i:
} // i
return(1);

}

/*****************************************/

unsigned long compare_A_B()
{
unsigned long i,j;
 
for (i=1;i<=n;i++)
{
  for (j=1;j<=n;j++)
  {
    if ( B[i][j] == 0 ) // not equal?
	  return(1);

    if ( A[i][j] > B[i][j] )
      return(0);

    if ( A[i][j] != B[i][j] ) // not equal
      return(1);
  } // j
} // i
return(1);
}

/*****************************************/

unsigned long compare_A_C()
{
unsigned long i,j;
 
for (i=1;i<=n;i++)
{
  for (j=1;j<=n;j++)
  {
    if ( C[i][j] == 0 ) // not equal
	  return(1);

    if ( A[i][j] > C[i][j] )
      return(0);

    if ( A[i][j] != C[i][j] ) // not equal
      return(1);
  } // j
} // i
return(1);
}


/*****************************************/


unsigned long perm()
{
 unsigned long i,j,k,m,l;
 unsigned long T[9];


 nf_gbl = n;
 for (m=n-1;m>0;m--) // nf means n! or n-factorial
    nf_gbl = nf_gbl*m;

 for (l=1;l<=n;l++)
   T[l] = 0;

 k = 1;

 j = 0;
//
// 40
//
 for (;;)
 {
   T[k] = T[k]+1;
   if ( T[k] > n )
   {
      T[k] = 0;
      k = k-1;
      if ( k == 0 )
        return(nf_gbl);

	 // printf("k=%d T[k]=%d\n",k,T[k]);
      continue; // to loop40
   }
//
// 50
//
   for (i=1;i<k;i++) // 60
   {
     if ( T[i] == T[k] )
       goto loop40;
   }
//
// 70
//
   if ( k != n )
   {
      k = k+1;
      goto loop40;
   }
//
// 80
//
   j = j+1;

   //printf("j=%5d   P= ",j);
   for (l=1;l<=n;l++)
   {
      P[j][l] = T[l];
   //printf("%1d ",P[j][l]);
   } // 90
   //printf("\n");
//
// 90
//
   for (l=1;l<=n;l++)
   {
      m = P[j][l];
      Q[j][m] = l;
   } // 100
   //printf("j=%5d   Q= ",j);
   for (l=1;l<=n;l++)
   {
     //printf("%1d ",Q[j][l]);
   }
   //printf("\n\n");
//
// 100
//
   if ( j == nf_gbl )
      return(nf_gbl);

loop40:
 }


}