```   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);
296:
297:
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] + " = " );
306:            System.out.print("  but   ");
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:
```