1:import java.util.*;
   2:import java.text.*;
   3:
   4:/**
   5:Looks for semigroups of a given order.  Uses brute force,
   6:so for order bigger than about 4, you need something else.
   7:**/
   8:public class SemiGroupList{
   9:   
  10:   /**
  11:   * Turns an array of length n*n into an n-by-n array
  12:   **/
  13:   protected static int[][] makeSquare(int[] longTab)
  14:   // throws IllegalArgumentException
  15:   {
  16:   /* if (longTab == null)
  17:         throw new IllegalArgumentException("argument longTab is null");
  18:
  19:      if (longTab.length == 0)
  20:         throw new IllegalArgumentException(
  21:         "argument longTab is of length zero");
  22:   */
  23:   
  24:      //Figure the floor of the squareroot of the length.  Do to
  25:      //numerical error, we may get something one less than expected.
  26:      int width = (int) Math.floor(Math.sqrt(longTab.length));
  27:      
  28:      //so we compenstate.
  29:      if ((width+1)*(width+1) <= longTab.length)
  30:         width++;
  31:      
  32:      if (width*width != longTab.length)
  33:         throw new IllegalArgumentException(
  34:            "argument longTab has length not a perfect square");
  35:      
  36:      int[][] squareTab = new int[width][width];
  37:      
  38:      int longIndex = 0;
  39:      for (int x = 0; x < width; x++){
  40:         for (int y=0; y < width; y++){
  41:            squareTab[x][y] = longTab[longIndex];
  42:            longIndex++;
  43:         }
  44:      }
  45:      
  46:      return squareTab;
  47:      
  48:   }
  49:   
  50:   /**
  51:   * This is silly.  Jave should have a way to print an integer where
  52:   * leading zeros become blanks.
  53:   **/
  54:   protected static String toStringFixedWidth(int input, int width)
  55:   // throws IllegalArgumentException
  56:   {
  57:   /* if (width < 0)
  58:         throw new IllegalArgumentException("width is negative.");
  59:   */
  60:      
  61:      String formatSymbol = "";
  62:      String blankString = "";
  63:      for (int n = 0; n < width; n++){
  64:         formatSymbol += "#";
  65:         blankString += " ";
  66:      }
  67:      DecimalFormat UpToThisWide = new DecimalFormat("###");
  68:      
  69:      String long_out = blankString + UpToThisWide.format(input);
  70:      String short_out = long_out.substring(long_out.length()-width);
  71:      
  72:      return short_out;
  73:      
  74:   }
  75:   
  76:   /**
  77:   * Prints out the table as an operation table.
  78:   **/
  79:   public static void printOp(int[][] table)
  80:   // throws IllegalArgumentException
  81:   {
  82:   /* if (table == null)
  83:         throw new IllegalArgumentException("null table as argument");
  84:   */
  85:   
  86:      int order = table.length;
  87:   
  88:      /* boolean isSquare = true;
  89:      for (int k = 0; k < order; k++)
  90:         isSquare = isSquare && (table[k] != null) && (table[k].length == order);
  91:      if (!isSquare)
  92:         throw new IllegalArgumentException("table is not square");
  93:   */
  94:      
  95:      System.out.print("     ");
  96:      for (int y = 0; y < order; y++)
  97:         System.out.print(" " + toStringFixedWidth(y,3));
  98:      System.out.println();
  99:
 100:      System.out.print("------");
 101:      for (int y = 0; y < order; y++)
 102:         System.out.print("----");     
 103:      System.out.println();
 104:      
 105:      for (int x = 0; x < order; x++){
 106:         System.out.print(" " + toStringFixedWidth(x,3) + "|");
 107:         for (int y = 0; y < order; y++)
 108:            System.out.print(" " + toStringFixedWidth(table[x][y],3));
 109:         System.out.println();
 110:      }
 111:      
 112:      
 113:   }
 114:      
 115:      
 116:   /**
 117:   * F   inds the "next" array with entrees between 0 and max.
 118:   * Returns null if the input is all length-1 (the "last array");
 119:   **/
 120:   public static int[]  nextList(int[] inList, int max)
 121:   // throws IllegalArgumentException
 122:   {
 123:      
 124:   /* if (inList == null)
 125:         throw new IllegalArgumentException("null array as argument");
 126:   */
 127:   
 128:      int len = inList.length;
 129:      
 130:   /* boolean numbersOk = true;
 131:      for (int k = 0; k < len; k++)
 132:         numbersOk = numbersOk && (0 <= inList[k] ) && (inList[k] <= max);
 133:      if (!numbersOk)
 134:         throw new IllegalArgumentException("array has elements not in range 0 to " + max);
 135:   */
 136:      
 137:      int[] outList = (int[]) inList.clone();
 138:      
 139:      //First try to increment the right-most non-zero postion.
 140:      //If so, put non-zero positions to the right down to 1.
 141:      boolean haveIncremented = false;
 142:      int j = len - 1;
 143:      while (j >= 0 && !haveIncremented){
 144:         if ( (0 < outList[j]) && (outList[j] < max) ){
 145:            outList[j]++;
 146:            haveIncremented = true;
 147:            for (int k = j+1; k < len; k++)
 148:               if (outList[k] > 0)
 149:                  outList[k] = 1;
 150:         }
 151:         j--;
 152:      }
 153:      if (haveIncremented)
 154:         return outList;
 155:      
 156:      //Special case:  input is [max].
 157:      if (len == 1)
 158:         return null;      
 159:      
 160:      //Now try to move one of the nonzero spots to the left.  If so,
 161:      //set the nonzero spots to 1, and move those to the left of the
 162:      //shift to be adjacent to the shift.
 163:      boolean haveShifted = false;
 164:      j = 1;
 165:      while (j < len && !haveShifted){
 166:         if ( outList[j-1] == 0   &&   outList[j] > 0){
 167:            outList[j-1] = 1;
 168:            outList[j] = 0;
 169:            haveShifted = true;
 170:            for (int k = j+1; k < len; k++)
 171:               if (outList[k] > 0)
 172:                  outList[k] = 1;
 173:            int numSpotsToLeft = 0;
 174:            for (int k=0; k < j - 1; k++)
 175:               if (outList[k] > 0)
 176:                  numSpotsToLeft++;
 177:            for (int k = 0; k < (j - 1 - numSpotsToLeft); k++)
 178:               outList[k] =0;
 179:            for (int k = (j - 1 - numSpotsToLeft); k < j-1; k++)
 180:               outList[k] =1;
 181:         }
 182:         j++;
 183:      }
 184:      if (haveShifted)
 185:         return outList;
 186:      
 187:      //Now try to increase the number of nonzero spots
 188:      int numPos = 0;
 189:      for (int k = 0; k < len; k++)
 190:         if (outList[k] > 0)
 191:            numPos++;
 192:      if (numPos < len){
 193:         for (int k = 0; k < (len - numPos - 1); k++)
 194:            outList[k]=0;
 195:         for (int k = (len - numPos - 1); k < len; k++)
 196:            outList[k]=1;
 197:         return outList;
 198:      }
 199:      
 200:      return null;
 201:      
 202:   }  
 203:   
 204:   
 205:   
 206:   /**
 207:   * Finds where the associative law "first' fails.  Returns null if this
 208:   * is actually a semigroup.
 209:   **/
 210:   public static int[]  associativeFailure(int[][] table)
 211:   // throws IllegalArgumentException
 212:   {
 213:   /* if (table == null)
 214:         throw new IllegalArgumentException("null table as argument");
 215:   */ 
 216:      int order = table.length;
 217:
 218:   /* //Check for a square table, all entrees in the range 0 to the width-1.
 219:      boolean isSquare = true;      
 220:      for (int k = 0; k < order; k++)
 221:         isSquare = isSquare && (table[k] != null) && (table[k].length == order);
 222:      if (!isSquare)
 223:         throw new IllegalArgumentException("table is not square");
 224:      boolean numbersOk = true;
 225:      for (int x = 0; x < order; x++)
 226:         for (int y = 0; y < order; y++)
 227:            numbersOk
 228:               = numbersOk && (0 <= table[x][y] ) && (table[x][y] < order);
 229:      if (!numbersOk)
 230:         throw new IllegalArgumentException("array has elements not in range 0 to " + (order - 1));
 231:   */
 232:   
 233:      int x,y,z;
 234:      boolean foundTrouble = false;
 235:      x = -1;
 236:      do{
 237:         x++;
 238:         y = -1;
 239:         do{
 240:            y++;
 241:            z = -1;
 242:            do{
 243:               z++;
 244:               foundTrouble = table[table[x][y]][z] != table[x][table[y][z]];
 245:            }while(z < order - 1 && !foundTrouble);
 246:         }while(y < order - 1 && !foundTrouble);
 247:      }while(x < order - 1 && !foundTrouble);
 248:      
 249:      if (foundTrouble)
 250:         return new int[]{x,y,z};
 251:      
 252:      return null;
 253:      
 254:   }
 255:
 256:
 257:
 258:
 259:   
 260:   public static void main(String[] args){
 261:      
 262:      if (args.length < 1){
 263:         System.out.println(
 264:            "One argument required; a natural number for the order."
 265:            +"semigroup to seek"
 266:         );
 267:         System.exit(0);
 268:      }
 269:      
 270:      
 271:      int order = -1;
 272:      try{
 273:         order = Integer.parseInt(args[0]);
 274:      }catch(NumberFormatException e){
 275:         System.out.println("Argument is not an integer.");
 276:         System.exit(0);
 277:      }
 278:      if (order <= 0){
 279:         System.out.println("Argument is not postive.");
 280:         System.exit(0);         
 281:      }
 282:      
 283:      boolean listSemigroupsOnly = (args.length >= 2) && args[1].equals("only");
 284:      
 285:      // Here we will store the n*n elements that make up
 286:      // the table for an operation.
 287:      int[] longTable;
 288:      
 289:      longTable = new int[order*order];
 290:      Arrays.fill(longTable, 0);
 291:      
 292:      
 293:      do{
 294:         int[][] operation = makeSquare(longTable);
 295:         int[] bad = associativeFailure(operation);
 296:         
 297:         
 298:         if (bad == null){
 299:            printOp(operation);
 300:            System.out.println("Semigroup");
 301:            System.out.println("\n~~~~~~~~~~~~~~~~~~~~\n");       
 302:         }else if (!listSemigroupsOnly){
 303:            printOp(operation);
 304:            System.out.print("(" + bad[0] + "*" + bad[1] + ")*" + bad[2] + " = " );
 305:            System.out.print(operation[operation[bad[0]][bad[1]]][bad[2]]);
 306:            System.out.print("  but   ");
 307:            System.out.print(bad[0] + "*(" + bad[1] + "*" + bad[2] + ") = " );
 308:            System.out.print(operation[bad[0]][operation[bad[1]][bad[2]]]);
 309:            System.out.println();
 310:            System.out.println("\n~~~~~~~~~~~~~~~~~~~~\n");       
 311:         }
 312:         longTable = nextList(longTable, order-1);
 313:      }while(longTable != null);
 314:      
 315:      
 316:      
 317:      
 318:      
 319:      
 320:   }
 321:
 322:}
 323:   
 324:   
 325: