import java.util.*; import java.text.*; /** Looks for semigroups of a given order. Uses brute force, so for order bigger than about 4, you need something else. **/ public class SemiGroupList{ /** * Turns an array of length n*n into an n-by-n array **/ protected static int[][] makeSquare(int[] longTab) // throws IllegalArgumentException { /* if (longTab == null) throw new IllegalArgumentException("argument longTab is null"); if (longTab.length == 0) throw new IllegalArgumentException( "argument longTab is of length zero"); */ //Figure the floor of the squareroot of the length. Do to //numerical error, we may get something one less than expected. int width = (int) Math.floor(Math.sqrt(longTab.length)); //so we compenstate. if ((width+1)*(width+1) <= longTab.length) width++; if (width*width != longTab.length) throw new IllegalArgumentException( "argument longTab has length not a perfect square"); int[][] squareTab = new int[width][width]; int longIndex = 0; for (int x = 0; x < width; x++){ for (int y=0; y < width; y++){ squareTab[x][y] = longTab[longIndex]; longIndex++; } } return squareTab; } /** * This is silly. Jave should have a way to print an integer where * leading zeros become blanks. **/ protected static String toStringFixedWidth(int input, int width) // throws IllegalArgumentException { /* if (width < 0) throw new IllegalArgumentException("width is negative."); */ String formatSymbol = ""; String blankString = ""; for (int n = 0; n < width; n++){ formatSymbol += "#"; blankString += " "; } DecimalFormat UpToThisWide = new DecimalFormat("###"); String long_out = blankString + UpToThisWide.format(input); String short_out = long_out.substring(long_out.length()-width); return short_out; } /** * Prints out the table as an operation table. **/ public static void printOp(int[][] table) // throws IllegalArgumentException { /* if (table == null) throw new IllegalArgumentException("null table as argument"); */ int order = table.length; /* boolean isSquare = true; for (int k = 0; k < order; k++) isSquare = isSquare && (table[k] != null) && (table[k].length == order); if (!isSquare) throw new IllegalArgumentException("table is not square"); */ System.out.print(" "); for (int y = 0; y < order; y++) System.out.print(" " + toStringFixedWidth(y,3)); System.out.println(); System.out.print("------"); for (int y = 0; y < order; y++) System.out.print("----"); System.out.println(); for (int x = 0; x < order; x++){ System.out.print(" " + toStringFixedWidth(x,3) + "|"); for (int y = 0; y < order; y++) System.out.print(" " + toStringFixedWidth(table[x][y],3)); System.out.println(); } } /** * F inds the "next" array with entrees between 0 and max. * Returns null if the input is all length-1 (the "last array"); **/ public static int[] nextList(int[] inList, int max) // throws IllegalArgumentException { /* if (inList == null) throw new IllegalArgumentException("null array as argument"); */ int len = inList.length; /* boolean numbersOk = true; for (int k = 0; k < len; k++) numbersOk = numbersOk && (0 <= inList[k] ) && (inList[k] <= max); if (!numbersOk) throw new IllegalArgumentException("array has elements not in range 0 to " + max); */ int[] outList = (int[]) inList.clone(); //First try to increment the right-most non-zero postion. //If so, put non-zero positions to the right down to 1. boolean haveIncremented = false; int j = len - 1; while (j >= 0 && !haveIncremented){ if ( (0 < outList[j]) && (outList[j] < max) ){ outList[j]++; haveIncremented = true; for (int k = j+1; k < len; k++) if (outList[k] > 0) outList[k] = 1; } j--; } if (haveIncremented) return outList; //Special case: input is [max]. if (len == 1) return null; //Now try to move one of the nonzero spots to the left. If so, //set the nonzero spots to 1, and move those to the left of the //shift to be adjacent to the shift. boolean haveShifted = false; j = 1; while (j < len && !haveShifted){ if ( outList[j-1] == 0 && outList[j] > 0){ outList[j-1] = 1; outList[j] = 0; haveShifted = true; for (int k = j+1; k < len; k++) if (outList[k] > 0) outList[k] = 1; int numSpotsToLeft = 0; for (int k=0; k < j - 1; k++) if (outList[k] > 0) numSpotsToLeft++; for (int k = 0; k < (j - 1 - numSpotsToLeft); k++) outList[k] =0; for (int k = (j - 1 - numSpotsToLeft); k < j-1; k++) outList[k] =1; } j++; } if (haveShifted) return outList; //Now try to increase the number of nonzero spots int numPos = 0; for (int k = 0; k < len; k++) if (outList[k] > 0) numPos++; if (numPos < len){ for (int k = 0; k < (len - numPos - 1); k++) outList[k]=0; for (int k = (len - numPos - 1); k < len; k++) outList[k]=1; return outList; } return null; } /** * Finds where the associative law "first' fails. Returns null if this * is actually a semigroup. **/ public static int[] associativeFailure(int[][] table) // throws IllegalArgumentException { /* if (table == null) throw new IllegalArgumentException("null table as argument"); */ int order = table.length; /* //Check for a square table, all entrees in the range 0 to the width-1. boolean isSquare = true; for (int k = 0; k < order; k++) isSquare = isSquare && (table[k] != null) && (table[k].length == order); if (!isSquare) throw new IllegalArgumentException("table is not square"); boolean numbersOk = true; for (int x = 0; x < order; x++) for (int y = 0; y < order; y++) numbersOk = numbersOk && (0 <= table[x][y] ) && (table[x][y] < order); if (!numbersOk) throw new IllegalArgumentException("array has elements not in range 0 to " + (order - 1)); */ int x,y,z; boolean foundTrouble = false; x = -1; do{ x++; y = -1; do{ y++; z = -1; do{ z++; foundTrouble = table[table[x][y]][z] != table[x][table[y][z]]; }while(z < order - 1 && !foundTrouble); }while(y < order - 1 && !foundTrouble); }while(x < order - 1 && !foundTrouble); if (foundTrouble) return new int[]{x,y,z}; return null; } public static void main(String[] args){ if (args.length < 1){ System.out.println( "One argument required; a natural number for the order." +"semigroup to seek" ); System.exit(0); } int order = -1; try{ order = Integer.parseInt(args[0]); }catch(NumberFormatException e){ System.out.println("Argument is not an integer."); System.exit(0); } if (order <= 0){ System.out.println("Argument is not postive."); System.exit(0); } boolean listSemigroupsOnly = (args.length >= 2) && args[1].equals("only"); // Here we will store the n*n elements that make up // the table for an operation. int[] longTable; longTable = new int[order*order]; Arrays.fill(longTable, 0); do{ int[][] operation = makeSquare(longTable); int[] bad = associativeFailure(operation); if (bad == null){ printOp(operation); System.out.println("Semigroup"); System.out.println("\n~~~~~~~~~~~~~~~~~~~~\n"); }else if (!listSemigroupsOnly){ printOp(operation); System.out.print("(" + bad[0] + "*" + bad[1] + ")*" + bad[2] + " = " ); System.out.print(operation[operation[bad[0]][bad[1]]][bad[2]]); System.out.print(" but "); System.out.print(bad[0] + "*(" + bad[1] + "*" + bad[2] + ") = " ); System.out.print(operation[bad[0]][operation[bad[1]][bad[2]]]); System.out.println(); System.out.println("\n~~~~~~~~~~~~~~~~~~~~\n"); } longTable = nextList(longTable, order-1); }while(longTable != null); } }