One Hat Cyber Team
Your IP :
216.73.216.24
Server IP :
194.44.31.54
Server :
Linux zen.imath.kiev.ua 4.18.0-553.77.1.el8_10.x86_64 #1 SMP Fri Oct 3 14:30:23 UTC 2025 x86_64
Server Software :
Apache/2.4.37 (Rocky Linux) OpenSSL/1.1.1k
PHP Version :
5.6.40
Buat File
|
Buat Folder
Eksekusi
Dir :
~
/
home
/
mellit
/
View File Name :
src.tar
src/ 0040700 0003665 0000062 00000000000 10056405670 0012545 5 ustar 00mellit guests 0000415 0000041 src/algebra/ 0040755 0003665 0000062 00000000000 07656475574 0014202 5 ustar 00mellit guests 0000415 0000041 src/algebra/linear/ 0040755 0003665 0000062 00000000000 10056446522 0015427 5 ustar 00mellit guests 0000415 0000041 src/algebra/linear/Sum.java 0100644 0003665 0000062 00000010202 10056446522 0017026 0 ustar 00mellit guests 0000415 0000041 package algebra.linear; import java.util.*; import algebra.numbers.Rational; import algebra.words.Alphabet; import algebra.words.Word; /** * @author Anton Mellit */ public class Sum { protected SortedMap map; public Sum() { map = new TreeMap(); } public void setZero() { map.clear(); } public void add(Object o) { add(o, Rational.ONE); } public void add(Object o, long k) { add(o, Rational.valueOf(k)); } public void add(Object o, Rational k) { if(!k.isZero()) { Rational x = (Rational) map.get(o); if(x!=null) { k = x.add(k); if(k.isZero()) { map.remove(o); } else { map.put(o, k); } } else { map.put(o, k); } } } public void add(Sum s) { add(s, Rational.ONE); } public void add(Sum s, long k) { add(s, Rational.valueOf(k)); } public void add(Sum s, Rational k) { for(Iterator i = s.map.entrySet().iterator(); i.hasNext();) { Map.Entry entry = (Map.Entry) i.next(); add(entry.getKey(), k.multiply((Rational) entry.getValue())); } } public void multiply(Rational k) { if(k.isZero()) { map.clear(); } for(Iterator i = map.entrySet().iterator(); i.hasNext();) { Map.Entry entry = (Map.Entry) i.next(); map.put(entry.getKey(), k.multiply((Rational) entry.getValue())); } } public String toString() { return toString(false); } public String toString(boolean skipMiddle) { if(map.entrySet().isEmpty()) return "0"; boolean first = true; String s = ""; int j = 0; boolean skipped = false; for (Iterator iterator = map.entrySet().iterator(); iterator.hasNext();) { if(j<20 || map.size()-j<20 || !skipMiddle) { Map.Entry entry = (Map.Entry) iterator.next(); Object o = entry.getKey(); Rational k = (Rational) entry.getValue(); if(skipped) { s = s + " ... "; } if(k.compareTo(Rational.ZERO)>=0) { if(!first) { s = s + " + "; } } else { if(!first) { s = s + " - "; } else { s = s + "- "; } } k = k.getAbs(); String ostr = o.toString(); if(!k.equals(Rational.ONE) || ostr.length()==0) { s = s + k; } s = s + ostr; first = false; skipped = false; } else { skipped = true; } j++; } return s; } public void normalize() { if(map.isEmpty()) return; Object w = map.lastKey(); Rational k = (Rational) map.get(w); multiply(k.invert()); } public Object getMainObject() { if(map.isEmpty()) { return null; } else { return map.lastKey(); } } public Set getObjects() { return map.keySet(); } public Rational getKoeff(Object o) { Rational k = (Rational) map.get(o); if(k==null) { return Rational.ZERO; } else { return k; } } public boolean isZero() { return map.isEmpty(); } public boolean equals(Object o) { if(o instanceof Sum) { Sum s = (Sum) o; Iterator i1 = map.entrySet().iterator(); Iterator i2 = s.map.entrySet().iterator(); while(i1.hasNext()) { if(!i2.hasNext()) { return false; } Map.Entry e1 = (Map.Entry) i1.next(); Map.Entry e2 = (Map.Entry) i2.next(); if(!e1.getKey().equals(e2.getKey())) { return false; } if(!e1.getValue().equals(e2.getValue())) { return false; } } if(i2.hasNext()) { return false; } return true; } else { return super.equals(o); } } public void modulo(Sum s) { Object main = s.getMainObject(); Rational k = ((Rational) map.get(main)).divide((Rational) s.map.get(main)); if(k!=null) { add(s, k.multiply(-1)); } } } src/algebra/linear/Sum.java~ 0100644 0003665 0000062 00000010547 07746551104 0017245 0 ustar 00mellit guests 0000415 0000041 package algebra.linear; import java.util.*; import algebra.numbers.Rational; import algebra.words.Alphabet; import algebra.words.Word; /** * @author Anton Mellit * * To change this generated comment edit the template variable "typecomment": * Window>Preferences>Java>Templates. * To enable and disable the creation of type comments go to * Window>Preferences>Java>Code Generation. */ public class Sum { protected SortedMap map; public Sum() { map = new TreeMap(); } public void setZero() { map.clear(); } public void add(Object o) { add(o, Rational.ONE); } public void add(Object o, long k) { add(o, Rational.valueOf(k)); } public void add(Object o, Rational k) { if(!k.isZero()) { Rational x = (Rational) map.get(o); if(x!=null) { k = x.add(k); if(k.isZero()) { map.remove(o); } else { map.put(o, k); } } else { map.put(o, k); } } } public void add(Sum s) { add(s, Rational.ONE); } public void add(Sum s, long k) { add(s, Rational.valueOf(k)); } public void add(Sum s, Rational k) { for(Iterator i = s.map.entrySet().iterator(); i.hasNext();) { Map.Entry entry = (Map.Entry) i.next(); add(entry.getKey(), k.multiply((Rational) entry.getValue())); } } public void multiply(Rational k) { if(k.isZero()) { map.clear(); } for(Iterator i = map.entrySet().iterator(); i.hasNext();) { Map.Entry entry = (Map.Entry) i.next(); map.put(entry.getKey(), k.multiply((Rational) entry.getValue())); } } public String toString() { return toString(false); } public String toString(boolean skipMiddle) { if(map.entrySet().isEmpty()) return "0"; boolean first = true; String s = ""; int j = 0; boolean skipped = false; for (Iterator iterator = map.entrySet().iterator(); iterator.hasNext();) { if(j<20 || map.size()-j<20 || !skipMiddle) { Map.Entry entry = (Map.Entry) iterator.next(); Object o = entry.getKey(); Rational k = (Rational) entry.getValue(); if(skipped) { s = s + " ... "; } if(k.compareTo(Rational.ZERO)>=0) { if(!first) { s = s + " + "; } } else { if(!first) { s = s + " - "; } else { s = s + "- "; } } k = k.getAbs(); String ostr = o.toString(); if(!k.equals(Rational.ONE) || ostr.length()==0) { s = s + k; } s = s + ostr; first = false; skipped = false; } else { skipped = true; } j++; } return s; } public void normalize() { if(map.isEmpty()) return; Object w = map.lastKey(); Rational k = (Rational) map.get(w); multiply(k.invert()); } public Object getMainObject() { if(map.isEmpty()) { return null; } else { return map.lastKey(); } } public Set getObjects() { return map.keySet(); } public Rational getKoeff(Object o) { Rational k = (Rational) map.get(o); if(k==null) { return Rational.ZERO; } else { return k; } } public boolean isZero() { return map.isEmpty(); } public boolean equals(Object o) { if(o instanceof Sum) { Sum s = (Sum) o; Iterator i1 = map.entrySet().iterator(); Iterator i2 = s.map.entrySet().iterator(); while(i1.hasNext()) { if(!i2.hasNext()) { return false; } Map.Entry e1 = (Map.Entry) i1.next(); Map.Entry e2 = (Map.Entry) i2.next(); if(!e1.getKey().equals(e2.getKey())) { return false; } if(!e1.getValue().equals(e2.getValue())) { return false; } } if(i2.hasNext()) { return false; } return true; } else { return super.equals(o); } } public void modulo(Sum s) { Object main = s.getMainObject(); Rational k = ((Rational) map.get(main)).divide((Rational) s.map.get(main)); if(k!=null) { add(s, k.multiply(-1)); } } } for(Iterator i = map.entrySet().iterator(); i.hasNext();) { Map.Entry entry = (Map.Entry) i.next(); map.put(entry.getKey(), k.multiply((Ratiosrc/algebra/numbers/ 0040755 0003665 0000062 00000000000 10056446006 0015625 5 ustar 00mellit guests 0000415 0000041 src/algebra/numbers/Rational.java 0100644 0003665 0000062 00000010731 10056446006 0020240 0 ustar 00mellit guests 0000415 0000041 package algebra.numbers; import java.math.BigInteger; import java.util.StringTokenizer; /** * @author Anton Mellit */ public class Rational implements Comparable{ private BigInteger num; private BigInteger denom; public static final Rational ZERO = new Rational(0, 1); public static final Rational ONE = new Rational(1, 1); public Rational(long num, long denom) { this.num = BigInteger.valueOf(num); this.denom = BigInteger.valueOf(denom); normalize(); } public Rational(BigInteger num, BigInteger denom) { this.num = num; this.denom = denom; normalize(); } public long getNum() { return num.longValue(); } public long getDenom() { return denom.longValue(); } protected void normalize() { if(denom.compareTo(BigInteger.ZERO)<0) { num = num.negate(); denom = denom.negate(); } else if(denom.equals(BigInteger.ZERO)) { throw new Error("Zero in denominator"); } BigInteger g = denom.gcd(num); num = num.divide(g); denom = denom.divide(g); } public Rational add(Rational r) { return new Rational(num.multiply(r.denom). add(denom.multiply(r.num)), denom.multiply(r.denom)); } public Rational add(Rational r, long k) { return new Rational(num.multiply(r.denom). add(denom.multiply(r.num).multiply(BigInteger.valueOf(k))), denom.multiply(r.denom)); } public Rational multiply(Rational r) { return new Rational(num.multiply(r.num), denom.multiply(r.denom)); } public Rational divide(Rational r) { return new Rational(num.multiply(r.denom), denom.multiply(r.num)); } public Rational multiply(long k) { return new Rational(num.multiply(BigInteger.valueOf(k)), denom); } public Rational divide(long k) { return new Rational(num, denom.multiply(BigInteger.valueOf(k))); } public String toString() { if(denom.equals(BigInteger.ONE)) { return String.valueOf(num); } else { return num + "/" + denom; } } public boolean isZero() { return num.equals(BigInteger.ZERO); } public boolean equals(Object obj) { if (obj instanceof Rational) { Rational rational = (Rational) obj; return (rational.num.equals(num)) && (rational.denom.equals(denom)); } else return false; } public int compareTo(Object o) { Rational rational = (Rational) o; return num.multiply(rational.denom).compareTo(denom.multiply(rational.num)); } public Rational getGCD(Rational r) { return new Rational(num.multiply(r.denom).gcd(denom.multiply(r.num)), denom.multiply(r.denom)); } public Rational getAbs() { return new Rational(num.abs(), denom); } public Rational invert() { return new Rational(denom, num); } public static Rational valueOf(long x) { return new Rational(x, 1); } public static Rational parse(String str) { StringTokenizer tok = new StringTokenizer(str, "-/", true); boolean minus = false; String num = "0"; String denom = "1"; boolean slash = false; while(tok.hasMoreTokens()) { String t; do { t = tok.nextToken().trim(); } while(tok.hasMoreTokens() && t.length()==0); if(t.equals("-")) { minus = true; } else if(t.equals("/")) { slash = true; } else if(t.length()>0) { if(!slash) { num = t; } else { denom = t; } } } long numVal = Long.parseLong(num); long denomVal = Long.parseLong(denom); if(minus) { numVal = -numVal; } return new Rational(numVal, denomVal); } public boolean isInteger() { return denom.equals(BigInteger.ONE); } public int hashCode() { return (int)((num.hashCode()<<16)^denom.hashCode()); } protected static long mod(long a, long b) { long c = a%b; if(c<0) { c = c + Math.abs(b); } return c; } protected static long gcd(long a, long b) { while(b!=0) { long c = mod(a, b); a = b; b = c; } return Math.abs(a); } } src/algebra/numbers/Rational.java~ 0100644 0003665 0000062 00000011276 07660146444 0020455 0 ustar 00mellit guests 0000415 0000041 package algebra.numbers; import java.math.BigInteger; import java.util.StringTokenizer; /** * @author Anton Mellit * * To change this generated comment edit the template variable "typecomment": * Window>Preferences>Java>Templates. * To enable and disable the creation of type comments go to * Window>Preferences>Java>Code Generation. */ public class Rational implements Comparable{ private BigInteger num; private BigInteger denom; public static final Rational ZERO = new Rational(0, 1); public static final Rational ONE = new Rational(1, 1); public Rational(long num, long denom) { this.num = BigInteger.valueOf(num); this.denom = BigInteger.valueOf(denom); normalize(); } public Rational(BigInteger num, BigInteger denom) { this.num = num; this.denom = denom; normalize(); } public long getNum() { return num.longValue(); } public long getDenom() { return denom.longValue(); } protected void normalize() { if(denom.compareTo(BigInteger.ZERO)<0) { num = num.negate(); denom = denom.negate(); } else if(denom.equals(BigInteger.ZERO)) { throw new Error("Zero in denominator"); } BigInteger g = denom.gcd(num); num = num.divide(g); denom = denom.divide(g); } public Rational add(Rational r) { return new Rational(num.multiply(r.denom). add(denom.multiply(r.num)), denom.multiply(r.denom)); } public Rational add(Rational r, long k) { return new Rational(num.multiply(r.denom). add(denom.multiply(r.num).multiply(BigInteger.valueOf(k))), denom.multiply(r.denom)); } public Rational multiply(Rational r) { return new Rational(num.multiply(r.num), denom.multiply(r.denom)); } public Rational divide(Rational r) { return new Rational(num.multiply(r.denom), denom.multiply(r.num)); } public Rational multiply(long k) { return new Rational(num.multiply(BigInteger.valueOf(k)), denom); } public Rational divide(long k) { return new Rational(num, denom.multiply(BigInteger.valueOf(k))); } public String toString() { if(denom.equals(BigInteger.ONE)) { return String.valueOf(num); } else { return num + "/" + denom; } } public boolean isZero() { return num.equals(BigInteger.ZERO); } public boolean equals(Object obj) { if (obj instanceof Rational) { Rational rational = (Rational) obj; return (rational.num.equals(num)) && (rational.denom.equals(denom)); } else return false; } public int compareTo(Object o) { Rational rational = (Rational) o; return num.multiply(rational.denom).compareTo(denom.multiply(rational.num)); } public Rational getGCD(Rational r) { return new Rational(num.multiply(r.denom).gcd(denom.multiply(r.num)), denom.multiply(r.denom)); } public Rational getAbs() { return new Rational(num.abs(), denom); } public Rational invert() { return new Rational(denom, num); } public static Rational valueOf(long x) { return new Rational(x, 1); } public static Rational parse(String str) { StringTokenizer tok = new StringTokenizer(str, "-/", true); boolean minus = false; String num = "0"; String denom = "1"; boolean slash = false; while(tok.hasMoreTokens()) { String t; do { t = tok.nextToken().trim(); } while(tok.hasMoreTokens() && t.length()==0); if(t.equals("-")) { minus = true; } else if(t.equals("/")) { slash = true; } else if(t.length()>0) { if(!slash) { num = t; } else { denom = t; } } } long numVal = Long.parseLong(num); long denomVal = Long.parseLong(denom); if(minus) { numVal = -numVal; } return new Rational(numVal, denomVal); } public boolean isInteger() { return denom.equals(BigInteger.ONE); } public int hashCode() { return (int)((num.hashCode()<<16)^denom.hashCode()); } protected static long mod(long a, long b) { long c = a%b; if(c<0) { c = c + Math.abs(b); } return c; } protected static long gcd(long a, long b) { while(b!=0) { long c = mod(a, b); a = b; b = c; } return Math.abs(a); } } ational(num, denom.multiply(BigInteger.valueOf(k))); } public String toString() { if(denom.equals(BigInteger.ONE)) { return String.valueOf(num); } else { return num + "/" + denom; } } public boolean isZero() { return num.equals(BigIsrc/algebra/words/ 0040755 0003665 0000062 00000000000 10056446412 0015311 5 ustar 00mellit guests 0000415 0000041 src/algebra/words/Alphabet.java 0100644 0003665 0000062 00000002112 10056446117 0017667 0 ustar 00mellit guests 0000415 0000041 package algebra.words; import java.util.*; /** * @author Anton Mellit */ public class Alphabet { private SortedMap nameToLetter; public Alphabet() { nameToLetter = new TreeMap(); } public void addLetter(Letter l) { nameToLetter.put(l.getName(), l); } public Letter getFirstLetter(String str) { SortedMap head = nameToLetter.headMap(str+" "); if(head.isEmpty()) { return null; } String subst = (String) head.lastKey(); if(str.startsWith(subst)) { return (Letter) nameToLetter.get(subst); } else { return null; } } public void dump() { System.out.println("Alphabet:"); for (Iterator iter = nameToLetter.entrySet().iterator(); iter.hasNext();) { Letter l = (Letter)((Map.Entry) iter.next()).getValue(); l.dump(); } } public Letter[] getLetters() { Letter[] res = new Letter[nameToLetter.size()]; int k = 0; for (Iterator iter = nameToLetter.entrySet().iterator(); iter.hasNext();) { Letter l = (Letter)((Map.Entry) iter.next()).getValue(); res[k] = l; k++; } return res; } } src/algebra/words/Letter.java 0100644 0003665 0000062 00000004214 10056446204 0017410 0 ustar 00mellit guests 0000415 0000041 package algebra.words; /** * @author Anton Mellit */ public class Letter implements Comparable{ private String name; private boolean central; private int level; private int index; public Letter(String name) { this.name = name; this.level = 0; this.index = 0; this.central = false; } public Letter(String name, boolean central) { this.name = name; this.level = central ? -1 : 0; this.central = central; this.index = 0; } public Letter(String name, boolean central, int level) { this.name = name; this.level = level; this.central = central; this.index = 0; } public Letter(String name, boolean central, int level, int index) { this.name = name; this.level = level; this.central = central; this.index = index; } /** * Returns the central. * @return boolean */ public boolean isCentral() { return central; } /** * Returns the highIndex. * @return int */ public int getLevel() { return level; } /** * Returns the lowIndex. * @return int */ public int getIndex() { return index; } /** * Returns the name. * @return String */ public String getName() { return name; } /** * Sets the central. * @param central The central to set */ public void setCentral(boolean central) { this.central = central; } /** * Sets the highIndex. * @param highIndex The highIndex to set */ public void setLevel(int highIndex) { this.level = highIndex; } /** * Sets the lowIndex. * @param lowIndex The lowIndex to set */ public void setIndex(int lowIndex) { this.index = lowIndex; } /** * @see java.lang.Comparable#compareTo(Object) */ public int compareTo(Object o) { Letter l = (Letter) o; if(level!=l.level) { return level-l.level; } if(index!=l.index) { return index-l.index; } return name.compareTo(l.name); } /** * @see java.lang.Object#toString() */ public String toString() { return name; } public void dump() { System.out.println(name+" "+(central?"Central":"Noncentral")+" weight "+level+" index "+index); } } src/algebra/words/Word.java 0100644 0003665 0000062 00000022060 10056446412 0017064 0 ustar 00mellit guests 0000415 0000041 package algebra.words; import java.util.Arrays; import java.util.Collection; import java.util.Iterator; import java.util.LinkedList; /** * @author Anton Mellit */ public class Word implements Comparable{ private Letter[] letters; private int centrals; public static final Word ONE = new Word(); public Word() { this.letters = new Letter[0]; normalize(); } public Word(Letter l) { this.letters = new Letter[1]; this.letters[0] = l; normalize(); } public Word(Letter[] letters) { this.letters = letters; normalize(); } public void normalize() { boolean ok = false; centrals = 0; while(!ok) { ok = true; for(int i = 0; i<letters.length-1; i++) { if(letters[i+1].isCentral()) { if(!letters[i].isCentral() || (letters[i].compareTo(letters[i+1])>0)) { ok = false; Letter z = letters[i]; letters[i] = letters[i+1]; letters[i+1] = z; } } } } for(int i = 0; i<letters.length; i++) { if(letters[i].isCentral()) { centrals++; } else { break; } } } public int getLength() { return letters.length; } public Word multiply(Word left, Word right) { int len = letters.length+left.letters.length+right.letters.length; Letter[] arr = new Letter[len]; int j = 0; for(int i = 0; i<left.letters.length; i++) { arr[j] = left.letters[i]; j++; } for(int i = 0; i<letters.length; i++) { arr[j] = letters[i]; j++; } for(int i = 0; i<right.letters.length; i++) { arr[j] = right.letters[i]; j++; } return new Word(arr); } protected int[] getNextLevel(int prevLevel) { int level = Integer.MIN_VALUE; int num = 0; for(int i = 0; i<letters.length; i++) { int l = letters[i].getLevel(); if(l>level && l<prevLevel) { level = l; num = 1; } else if(l==level) { num++; } } int[] ans = {level, num}; return ans; } protected int compareToLevel(Word w, int level) { int i1 = 0; int i2 = 0; while(true) { while(i1<letters.length && letters[i1].getLevel()<level) i1++; if(i1==letters.length) break; while(i2<w.letters.length && w.letters[i2].getLevel()<level) i2++; int c = letters[i1].compareTo(w.letters[i2]); if(c!=0) return c; i1++; i2++; } return 0; } /** * @see java.lang.Comparable#compareTo(Object) */ public int compareTo(Object o) { Word w = (Word) o; int lastLevel = Integer.MAX_VALUE; while(lastLevel>Integer.MIN_VALUE) { int[] a1 = getNextLevel(lastLevel); int[] a2 = w.getNextLevel(lastLevel); if(a1[0]!=a2[0]) { if(a1[0]<a2[0]) { return -1; } else { return 1; } } lastLevel = a1[0]; if(a1[1]!=a2[1]) { return a1[1]-a2[1]; } int c = compareToLevel(w, lastLevel); if(c!=0) { return c; } } return 0; } /** * @see java.lang.Object#equals(Object) */ public boolean equals(Object obj) { if(obj instanceof Word) { Word w = (Word) obj; return Arrays.equals(letters, w.letters); } return super.equals(obj); } /** * @see java.lang.Object#toString() */ public String toString() { if(letters.length==0) return ""; String s = ""; Letter lastLetter = null; int lastCount = 0; for(int i = 0; i<letters.length; i++) { Letter letter = letters[i]; if(letter==lastLetter) { lastCount++; } else { if(lastCount!=0) { s = s + lastLetter; if(lastCount!=1) { s = s + "^"+lastCount; } } lastCount = 1; lastLetter = letter; } } s = s + lastLetter; if(lastCount!=1) { s = s + "^"+lastCount; } return s; } public Word subword(int begin, int end) { Letter[] l = new Letter[end-begin]; for(int i = begin; i<end; i++) { l[i-begin] = letters[i]; } return new Word(l); } protected boolean checkCentrals(Word w) { int i = 0; int j = 0; while(i<w.centrals) { while(j<centrals && letters[j].compareTo(w.letters[i])<0) { j++; } if(j==centrals || letters[j]!=w.letters[i]) { return false; } i++; j++; } return true; } public int find(Word w, int from) { if(!checkCentrals(w)) { return -1; } while(from<=(letters.length-centrals-w.letters.length+w.centrals)) { boolean eq = true; for(int i = 0; i<w.letters.length-w.centrals; i++) { if(letters[centrals+from+i]!=w.letters[w.centrals+i]) { eq = false; break; } } if(eq) { return from; } from++; } return -1; } public Word[] divide(Word w, int from) { int len1 = centrals-w.centrals+from; int len2 = letters.length-w.letters.length-len1; Letter[] arr1 = new Letter[len1]; Letter[] arr2 = new Letter[len2]; int j = 0; int pos = 0; for(int i = 0; i<centrals; i++) { if(j<w.centrals && w.letters[j]==letters[i]) { j++; } else { arr1[pos] = letters[i]; pos++; } } for(int i = 0; i<from; i++) { arr1[pos+i] = letters[centrals+i]; } int delta = letters.length-len2; for(int i = 0; i<len2; i++) { arr2[i] = letters[delta+i]; } Word[] res = {new Word(arr1), new Word(arr2)}; return res; } public static class Split { public Word left; public Word center; public Word right; public Split(Word left, Word center, Word right) { this.left = left; this.center = center; this.right = right; } } protected void splitCenters(Word w, LinkedList left, LinkedList center, LinkedList right) { int i = 0; int j = 0; while(i<centrals || j<w.centrals) { if(i<centrals && j<w.centrals && letters[i]==w.letters[j]) { center.add(letters[i]); i++; j++; } else if(j==w.centrals || (i<centrals && letters[i].compareTo(w.letters[j])<0)) { left.add(letters[i]); i++; } else { right.add(w.letters[j]); j++; } } } protected boolean checkSplit(Word w, int offset) { for(int i = 0; i+offset+centrals<letters.length; i++) { if(letters[i+offset+centrals]!=w.letters[i+w.centrals]) { return false; } } return true; } protected static void fillArray(Letter[] arr, Collection col) { int pos = 0; for(Iterator i = col.iterator(); i.hasNext();) { arr[pos] = (Letter) i.next(); pos++; } } protected Split makeSplit(Word w, int offset, LinkedList cleft, LinkedList ccenter, LinkedList cright) { int centerSize = letters.length-centrals-offset; int len1 = offset+cleft.size(); int len2 = centerSize+ccenter.size(); int len3 = w.letters.length-w.centrals-centerSize+cright.size(); Letter[] arr1 = new Letter[len1]; Letter[] arr2 = new Letter[len2]; Letter[] arr3 = new Letter[len3]; fillArray(arr1, cleft); fillArray(arr2, ccenter); fillArray(arr3, cright); for(int i = 0; i<offset; i++) { arr1[cleft.size()+i] = letters[centrals+i]; } for(int i = 0; i<centerSize; i++) { arr2[ccenter.size()+i] = letters[centrals+offset+i]; } for(int i = 0; i<w.letters.length-w.centrals-centerSize; i++) { arr3[cright.size()+i] = w.letters[w.centrals+centerSize+i]; } return new Split(new Word(arr1), new Word(arr2), new Word(arr3)); } public Collection getAllSplits(Word w) { LinkedList splits = new LinkedList(); LinkedList left = new LinkedList(); LinkedList center = new LinkedList(); LinkedList right = new LinkedList(); splitCenters(w, left, center, right); int maxcenter = Math.min(letters.length-centrals, w.letters.length-w.centrals); int mincenter = 1; if(center.size()>0) { mincenter = 0; } for(int offset = letters.length-centrals-maxcenter; offset<=letters.length-centrals-mincenter; offset++) { if(checkSplit(w, offset)) { Split s = makeSplit(w, offset, left, center, right); if(s.left.getLength()+s.right.getLength()>0) { splits.add(s); } } } return splits; } public Letter[] getLetters() { return letters; } public static Word parseString(String s, Alphabet abc) { LinkedList letters = new LinkedList(); int pos = 0; while(pos<s.length()) { while(pos<s.length() && (s.charAt(pos)==' ' || s.charAt(pos)=='*')) { pos++; } if(pos==s.length()) { break; } Letter l = abc.getFirstLetter(s.substring(pos)); if(l==null) return null; pos+=l.getName().length(); if(pos<s.length() && s.charAt(pos)=='^') { pos++; int pos1 = pos; while(pos<s.length() && s.charAt(pos)<='9' && s.charAt(pos)>='0') pos++; int power = Integer.parseInt(s.substring(pos1, pos)); for(int i = 0; i<power; i++) { letters.add(l); } } else { letters.add(l); } } Letter[] arr = new Letter[letters.size()]; Iterator i = letters.iterator(); int j = 0; while(i.hasNext()) { arr[j] = (Letter) i.next(); j++; } return new Word(arr); } } src/algebra/words/Alphabet.java~ 0100644 0003665 0000062 00000002457 07746553460 0020115 0 ustar 00mellit guests 0000415 0000041 package algebra.words; import java.util.*; /** * @author Anton Mellit * * To change this generated comment edit the template variable "typecomment": * Window>Preferences>Java>Templates. * To enable and disable the creation of type comments go to * Window>Preferences>Java>Code Generation. */ public class Alphabet { private SortedMap nameToLetter; public Alphabet() { nameToLetter = new TreeMap(); } public void addLetter(Letter l) { nameToLetter.put(l.getName(), l); } public Letter getFirstLetter(String str) { SortedMap head = nameToLetter.headMap(str+" "); if(head.isEmpty()) { return null; } String subst = (String) head.lastKey(); if(str.startsWith(subst)) { return (Letter) nameToLetter.get(subst); } else { return null; } } public void dump() { System.out.println("Alphabet:"); for (Iterator iter = nameToLetter.entrySet().iterator(); iter.hasNext();) { Letter l = (Letter)((Map.Entry) iter.next()).getValue(); l.dump(); } } public Letter[] getLetters() { Letter[] res = new Letter[nameToLetter.size()]; int k = 0; for (Iterator iter = nameToLetter.entrySet().iterator(); iter.hasNext();) { Letter l = (Letter)((Map.Entry) iter.next()).getValue(); res[k] = l; k++; } return res; } } src/algebra/words/Letter.java~ 0100644 0003665 0000062 00000004561 07746550430 0017624 0 ustar 00mellit guests 0000415 0000041 package algebra.words; /** * @author Anton Mellit * * To change this generated comment edit the template variable "typecomment": * Window>Preferences>Java>Templates. * To enable and disable the creation of type comments go to * Window>Preferences>Java>Code Generation. */ public class Letter implements Comparable{ private String name; private boolean central; private int level; private int index; public Letter(String name) { this.name = name; this.level = 0; this.index = 0; this.central = false; } public Letter(String name, boolean central) { this.name = name; this.level = central ? -1 : 0; this.central = central; this.index = 0; } public Letter(String name, boolean central, int level) { this.name = name; this.level = level; this.central = central; this.index = 0; } public Letter(String name, boolean central, int level, int index) { this.name = name; this.level = level; this.central = central; this.index = index; } /** * Returns the central. * @return boolean */ public boolean isCentral() { return central; } /** * Returns the highIndex. * @return int */ public int getLevel() { return level; } /** * Returns the lowIndex. * @return int */ public int getIndex() { return index; } /** * Returns the name. * @return String */ public String getName() { return name; } /** * Sets the central. * @param central The central to set */ public void setCentral(boolean central) { this.central = central; } /** * Sets the highIndex. * @param highIndex The highIndex to set */ public void setLevel(int highIndex) { this.level = highIndex; } /** * Sets the lowIndex. * @param lowIndex The lowIndex to set */ public void setIndex(int lowIndex) { this.index = lowIndex; } /** * @see java.lang.Comparable#compareTo(Object) */ public int compareTo(Object o) { Letter l = (Letter) o; if(level!=l.level) { return level-l.level; } if(index!=l.index) { return index-l.index; } return name.compareTo(l.name); } /** * @see java.lang.Object#toString() */ public String toString() { return name; } public void dump() { System.out.println(name+" "+(central?"Central":"Noncentral")+" weight "+level+" index "+index); } } src/algebra/words/Word.java~ 0100644 0003665 0000062 00000022415 07746562120 0017275 0 ustar 00mellit guests 0000415 0000041 package algebra.words; import java.util.Arrays; import java.util.Collection; import java.util.Iterator; import java.util.LinkedList; /** * @author Anton Mellit * * To change this generated comment edit the template variable "typecomment": * Window>Preferences>Java>Templates. * To enable and disable the creation of type comments go to * Window>Preferences>Java>Code Generation. */ public class Word implements Comparable{ private Letter[] letters; private int centrals; public static final Word ONE = new Word(); public Word() { this.letters = new Letter[0]; normalize(); } public Word(Letter l) { this.letters = new Letter[1]; this.letters[0] = l; normalize(); } public Word(Letter[] letters) { this.letters = letters; normalize(); } public void normalize() { boolean ok = false; centrals = 0; while(!ok) { ok = true; for(int i = 0; i<letters.length-1; i++) { if(letters[i+1].isCentral()) { if(!letters[i].isCentral() || (letters[i].compareTo(letters[i+1])>0)) { ok = false; Letter z = letters[i]; letters[i] = letters[i+1]; letters[i+1] = z; } } } } for(int i = 0; i<letters.length; i++) { if(letters[i].isCentral()) { centrals++; } else { break; } } } public int getLength() { return letters.length; } public Word multiply(Word left, Word right) { int len = letters.length+left.letters.length+right.letters.length; Letter[] arr = new Letter[len]; int j = 0; for(int i = 0; i<left.letters.length; i++) { arr[j] = left.letters[i]; j++; } for(int i = 0; i<letters.length; i++) { arr[j] = letters[i]; j++; } for(int i = 0; i<right.letters.length; i++) { arr[j] = right.letters[i]; j++; } return new Word(arr); } protected int[] getNextLevel(int prevLevel) { int level = Integer.MIN_VALUE; int num = 0; for(int i = 0; i<letters.length; i++) { int l = letters[i].getLevel(); if(l>level && l<prevLevel) { level = l; num = 1; } else if(l==level) { num++; } } int[] ans = {level, num}; return ans; } protected int compareToLevel(Word w, int level) { int i1 = 0; int i2 = 0; while(true) { while(i1<letters.length && letters[i1].getLevel()<level) i1++; if(i1==letters.length) break; while(i2<w.letters.length && w.letters[i2].getLevel()<level) i2++; int c = letters[i1].compareTo(w.letters[i2]); if(c!=0) return c; i1++; i2++; } return 0; } /** * @see java.lang.Comparable#compareTo(Object) */ public int compareTo(Object o) { Word w = (Word) o; int lastLevel = Integer.MAX_VALUE; while(lastLevel>Integer.MIN_VALUE) { int[] a1 = getNextLevel(lastLevel); int[] a2 = w.getNextLevel(lastLevel); if(a1[0]!=a2[0]) { if(a1[0]<a2[0]) { return -1; } else { return 1; } } lastLevel = a1[0]; if(a1[1]!=a2[1]) { return a1[1]-a2[1]; } int c = compareToLevel(w, lastLevel); if(c!=0) { return c; } } return 0; } /** * @see java.lang.Object#equals(Object) */ public boolean equals(Object obj) { if(obj instanceof Word) { Word w = (Word) obj; return Arrays.equals(letters, w.letters); } return super.equals(obj); } /** * @see java.lang.Object#toString() */ public String toString() { if(letters.length==0) return ""; String s = ""; Letter lastLetter = null; int lastCount = 0; for(int i = 0; i<letters.length; i++) { Letter letter = letters[i]; if(letter==lastLetter) { lastCount++; } else { if(lastCount!=0) { s = s + lastLetter; if(lastCount!=1) { s = s + "^"+lastCount; } } lastCount = 1; lastLetter = letter; } } s = s + lastLetter; if(lastCount!=1) { s = s + "^"+lastCount; } return s; } public Word subword(int begin, int end) { Letter[] l = new Letter[end-begin]; for(int i = begin; i<end; i++) { l[i-begin] = letters[i]; } return new Word(l); } protected boolean checkCentrals(Word w) { int i = 0; int j = 0; while(i<w.centrals) { while(j<centrals && letters[j].compareTo(w.letters[i])<0) { j++; } if(j==centrals || letters[j]!=w.letters[i]) { return false; } i++; j++; } return true; } public int find(Word w, int from) { if(!checkCentrals(w)) { return -1; } while(from<=(letters.length-centrals-w.letters.length+w.centrals)) { boolean eq = true; for(int i = 0; i<w.letters.length-w.centrals; i++) { if(letters[centrals+from+i]!=w.letters[w.centrals+i]) { eq = false; break; } } if(eq) { return from; } from++; } return -1; } public Word[] divide(Word w, int from) { int len1 = centrals-w.centrals+from; int len2 = letters.length-w.letters.length-len1; Letter[] arr1 = new Letter[len1]; Letter[] arr2 = new Letter[len2]; int j = 0; int pos = 0; for(int i = 0; i<centrals; i++) { if(j<w.centrals && w.letters[j]==letters[i]) { j++; } else { arr1[pos] = letters[i]; pos++; } } for(int i = 0; i<from; i++) { arr1[pos+i] = letters[centrals+i]; } int delta = letters.length-len2; for(int i = 0; i<len2; i++) { arr2[i] = letters[delta+i]; } Word[] res = {new Word(arr1), new Word(arr2)}; return res; } public static class Split { public Word left; public Word center; public Word right; public Split(Word left, Word center, Word right) { this.left = left; this.center = center; this.right = right; } } protected void splitCenters(Word w, LinkedList left, LinkedList center, LinkedList right) { int i = 0; int j = 0; while(i<centrals || j<w.centrals) { if(i<centrals && j<w.centrals && letters[i]==w.letters[j]) { center.add(letters[i]); i++; j++; } else if(j==w.centrals || (i<centrals && letters[i].compareTo(w.letters[j])<0)) { left.add(letters[i]); i++; } else { right.add(w.letters[j]); j++; } } } protected boolean checkSplit(Word w, int offset) { for(int i = 0; i+offset+centrals<letters.length; i++) { if(letters[i+offset+centrals]!=w.letters[i+w.centrals]) { return false; } } return true; } protected static void fillArray(Letter[] arr, Collection col) { int pos = 0; for(Iterator i = col.iterator(); i.hasNext();) { arr[pos] = (Letter) i.next(); pos++; } } protected Split makeSplit(Word w, int offset, LinkedList cleft, LinkedList ccenter, LinkedList cright) { int centerSize = letters.length-centrals-offset; int len1 = offset+cleft.size(); int len2 = centerSize+ccenter.size(); int len3 = w.letters.length-w.centrals-centerSize+cright.size(); Letter[] arr1 = new Letter[len1]; Letter[] arr2 = new Letter[len2]; Letter[] arr3 = new Letter[len3]; fillArray(arr1, cleft); fillArray(arr2, ccenter); fillArray(arr3, cright); for(int i = 0; i<offset; i++) { arr1[cleft.size()+i] = letters[centrals+i]; } for(int i = 0; i<centerSize; i++) { arr2[ccenter.size()+i] = letters[centrals+offset+i]; } for(int i = 0; i<w.letters.length-w.centrals-centerSize; i++) { arr3[cright.size()+i] = w.letters[w.centrals+centerSize+i]; } return new Split(new Word(arr1), new Word(arr2), new Word(arr3)); } public Collection getAllSplits(Word w) { LinkedList splits = new LinkedList(); LinkedList left = new LinkedList(); LinkedList center = new LinkedList(); LinkedList right = new LinkedList(); splitCenters(w, left, center, right); int maxcenter = Math.min(letters.length-centrals, w.letters.length-w.centrals); int mincenter = 1; if(center.size()>0) { mincenter = 0; } for(int offset = letters.length-centrals-maxcenter; offset<=letters.length-centrals-mincenter; offset++) { if(checkSplit(w, offset)) { Split s = makeSplit(w, offset, left, center, right); if(s.left.getLength()+s.right.getLength()>0) { splits.add(s); } } } return splits; } public Letter[] getLetters() { return letters; } public static Word parseString(String s, Alphabet abc) { LinkedList letters = new LinkedList(); int pos = 0; while(pos<s.length()) { while(pos<s.length() && (s.charAt(pos)==' ' || s.charAt(pos)=='*')) { pos++; } if(pos==s.length()) { break; } Letter l = abc.getFirstLetter(s.substring(pos)); if(l==null) return null; pos+=l.getName().length(); if(pos<s.length() && s.charAt(pos)=='^') { pos++; int pos1 = pos; while(pos<s.length() && s.charAt(pos)<='9' && s.charAt(pos)>='0') pos++; int power = Integer.parseInt(s.substring(pos1, pos)); for(int i = 0; i<power; i++) { letters.add(l); } } else { letters.add(l); } } Letter[] arr = new Letter[letters.size()]; Iterator i = letters.iterator(); int j = 0; while(i.hasNext()) { arr[j] = (Letter) i.next(); j++; } return new Word(arr); } } vel); int[] a2 = w.getNextLevel(lastLevel); if(a1[0]!=a2[0]) { if(a1[0]<a2[0]) { return -1; } else { return 1; } } lastLevel = a1[0]; if(a1[1]!=a2[1]) { return a1[1]-a2[1]; } int c = src/calculus/ 0040755 0003665 0000062 00000000000 10056447417 0014377 5 ustar 00mellit guests 0000415 0000041 src/calculus/CenterAnalysis.java 0100644 0003665 0000062 00000007204 10056447417 0020166 0 ustar 00mellit guests 0000415 0000041 package calculus; import java.util.Collection; import java.util.Iterator; import java.util.Map; import java.util.Set; import java.util.TreeMap; import java.util.TreeSet; import algebra.linear.Sum; import algebra.numbers.Rational; import algebra.words.Letter; import algebra.words.Word; /** * @author Anton Mellit */ class Commutator { public WordSum x; public Sum values; } public class CenterAnalysis { protected Map comms; protected Letter[] letters; protected Letter[] generators; protected Set wordsToProcess; protected Set nextWords; protected Collection groebnerBase; protected boolean dump; protected int length; public CenterAnalysis(Letter[] generators, Letter[] letters, Collection groebnerBase) { comms = new TreeMap(); this.letters = letters; this.generators = generators; wordsToProcess = new TreeSet(); nextWords = new TreeSet(); this.groebnerBase = groebnerBase; length = 0; } /** * Sets the dump. * @param dump The dump to set */ public void setDump(boolean dump) { this.dump = dump; } protected void init() { for(int i = 0; i<letters.length; i++) { if(!letters[i].isCentral()) { nextWords.add(new Word(letters[i])); } } length = 1; } protected WordSum process() { if(dump) { System.out.println("Processing words with length "+length+" ("+nextWords.size()+" words)"); } wordsToProcess.clear(); wordsToProcess.addAll(nextWords); nextWords.clear(); for(Iterator i = wordsToProcess.iterator(); i.hasNext(); ) { Word w = (Word) i.next(); if(isBaseWord(w)) { addWords(w); Commutator comm = addCommutator(w); if(comm.values.isZero()) { if(dump) { System.out.println("Central element found: "+comm.x); } return comm.x; } } } length++; return null; } public WordSum findCenter() { init(); WordSum answer = null; while(answer==null && !nextWords.isEmpty() && length<31) { answer = process(); } return answer; } protected boolean isBaseWord(Word w) { for(Iterator i = groebnerBase.iterator(); i.hasNext(); ) { WordSum s = (WordSum) i.next(); if(w.find((Word) s.getMainObject(), 0)>=0) { return false; } } return true; } protected void addWords(Word w) { for(int i = 0; i<letters.length; i++) { nextWords.add(w.multiply(new Word(letters[i]), Word.ONE)); } } protected Commutator addCommutator(Word w) { Commutator comm = new Commutator(); comm.values = new Sum(); for(int i = 0; i<generators.length; i++) { addCommutator(comm.values, w, new Word(generators[i])); } comm.x = new WordSum(); comm.x.add(w); if(!comm.values.isZero()) { reduce(comm); } if(!comm.values.isZero()) { comms.put(comm.values.getMainObject(), comm); } return comm; } protected void addCommutator(Sum s, Word w, Word x) { WordSum c = new WordSum(); c.add(w.multiply(x, Word.ONE)); c.add(w.multiply(Word.ONE, x), -1); c.reduce(groebnerBase); for(Iterator i = c.getObjects().iterator(); i.hasNext(); ) { Object o = i.next(); s.add(x.toString()+": "+o, c.getKoeff(o)); } } protected void reduce(Commutator comm) { boolean finished = false; do { Object main = comm.values.getMainObject(); Commutator mod = (Commutator) comms.get(main); if(mod!=null) { Rational k = comm.values.getKoeff(main).divide( mod.values.getKoeff(mod.values.getMainObject())).multiply(-1); comm.values.add(mod.values, k); comm.x.add(mod.x, k); } else { finished = true; } } while(!finished && !comm.values.isZero()); } } src/calculus/Groebner.java 0100644 0003665 0000062 00000011401 10056447041 0016770 0 ustar 00mellit guests 0000415 0000041 package calculus; import java.util.Collection; import java.util.Comparator; import java.util.Iterator; import java.util.LinkedList; import java.util.Set; import java.util.TreeSet; import algebra.numbers.Rational; import algebra.words.Word; /** * @author Anton Mellit */ class SplitComp implements Comparator { public int compare(Object o1, Object o2) { Word.Split s1 = (Word.Split) o1; Word.Split s2 = (Word.Split) o2; int c = s1.left.compareTo(s2.left); if(c!=0) return c; c = s1.center.compareTo(s2.center); if(c!=0) return c; c = s1.right.compareTo(s2.right); return c; } } class Composition { public WordSum s1; public WordSum s2; public Word.Split split; } public class Groebner { protected Collection relations; protected Set splitsUsed; protected Collection newRelations; protected Collection newCompositions; protected boolean dump; public Groebner() { relations = new LinkedList(); splitsUsed = new TreeSet(new SplitComp()); newRelations = new LinkedList(); newCompositions = new LinkedList(); } /** * Sets the dump. * @param dump The dump to set */ public void setDump(boolean dump) { this.dump = dump; } public void addRelation(WordSum rel) { rel.reduce(relations); if(!rel.isZero()) { rel.normalize(); newRelations.add(rel); if(dump) { // System.out.println("Added new relation "+rel); } } } protected boolean pairwiseReduce() { if(dump) { System.out.println("Pairwise reduce ("+relations.size()+" relations)"); } boolean changed = false; int k = 0; for(Iterator i1 = relations.iterator(); i1.hasNext(); ) { k++; WordSum s1 = (WordSum) i1.next(); if(s1.isZero()) { i1.remove(); changed = true; } else { for(Iterator i2 = relations.iterator(); i2.hasNext(); ) { WordSum s2 = (WordSum) i2.next(); if(s1!=s2) { if(s2.reduce(s1)) { s2.normalize(); changed = true; } } } } if(k%10==0) { System.out.println("Ready: "+k); } } return changed; } protected void fullReduce() { if(dump) { System.out.println("Reducing all relations"); } while(pairwiseReduce()); } public void dumpStatus() { if(dump) { System.out.println("Have "+relations.size()+" relations:"); for(Iterator i1 = relations.iterator(); i1.hasNext(); ) { WordSum s1 = (WordSum) i1.next(); System.out.println(s1.toString(true)); } } } public void mergeRelations() { relations.addAll(newRelations); newRelations.clear(); fullReduce(); dumpStatus(); } protected void makeCompositions() { for(Iterator i1 = relations.iterator(); i1.hasNext(); ) { WordSum s1 = (WordSum) i1.next(); Word m1 = (Word) s1.getMainObject(); for(Iterator i2 = relations.iterator(); i2.hasNext(); ) { WordSum s2 = (WordSum) i2.next(); Word m2 = (Word) s2.getMainObject(); Collection splits = m1.getAllSplits(m2); for(Iterator i3 = splits.iterator(); i3.hasNext(); ) { Word.Split split = (Word.Split) i3.next(); if(!splitsUsed.contains(split)) { splitsUsed.add(split); addComposition(s1, s2, split); } } } } } protected void addComposition(WordSum s1, WordSum s2, Word.Split split) { if(dump) { System.out.println("Scheduled composition "+splitToString(split)); } Composition c = new Composition(); c.s1 = s1; c.s2 = s2; c.split = split; newCompositions.add(c); } protected String splitToString(Word.Split split) { return split.left.toString()+"|"+split.center+"|"+split.right; } protected void mergeCompositions() { int j = 0; for(Iterator i = newCompositions.iterator(); i.hasNext(); ) { mergeComposition((Composition) i.next(), j); j++; } newCompositions.clear(); } protected void mergeComposition(Composition c, int i) { if(dump) { System.out.println("Making composition "+splitToString(c.split)+" ("+i+"/"+ newCompositions.size()+")"); } WordSum s = new WordSum(); s.add(c.s1, Word.ONE, c.split.right, Rational.valueOf(1)); s.add(c.s2, c.split.left, Word.ONE, Rational.valueOf(-1)); addRelation(s); } public boolean fullCompose() { makeCompositions(); boolean changed = !newCompositions.isEmpty(); mergeCompositions(); return changed; } public void groebnerClosure() { boolean changed; do { changed = fullCompose(); mergeRelations(); } while(changed); } public Collection getRelations() { return relations; } public void dump() { System.out.println("Relations:"); for (Iterator iter = relations.iterator(); iter.hasNext();) { WordSum ws = (WordSum) iter.next(); System.out.println(ws); } } } src/calculus/Main.java 0100644 0003665 0000062 00000022045 07746561064 0016135 0 ustar 00mellit guests 0000415 0000041 package calculus; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Iterator; import java.util.LinkedList; import java.util.Vector; import algebra.numbers.Rational; import algebra.words.Alphabet; import algebra.words.Letter; import algebra.words.Word; /** * @author Anton Mellit * * To change this generated comment edit the template variable "typecomment": * Window>Preferences>Java>Templates. * To enable and disable the creation of type comments go to * Window>Preferences>Java>Code Generation. */ public class Main { public static void printBaseWords(String letters, String[] g, Alphabet abc) { Vector words = new Vector(); words.add(""); int k = 0; for(int i = 0; i<words.size(); i++) { String s = (String) words.get(i); System.out.print(Word.parseString(s, abc).toString()+", "); for(int j = 0; j<letters.length(); j++) { String s2 = s+letters.substring(j, j+1); boolean ok = true; for(int jj = 0; jj<g.length; jj++) { if(s2.indexOf(g[jj])>=0) { ok = false; break; } } if(ok) { words.add(s2); } } } System.out.println(); System.out.println("Total: "+words.size()); } public static void main(String[] args) { Alphabet abc = new Alphabet(); abc.addLetter(new Letter("A")); abc.addLetter(new Letter("B")); abc.addLetter(new Letter("C")); // abc.addLetter(new Letter("D")); // abc.addLetter(new Letter("z0", false, 50, 1)); // abc.addLetter(new Letter("z1", false, 50, 2)); // abc.addLetter(new Letter("z2", false, 50, 3)); // abc.addLetter(new Letter("z3", false, 50, 4)); // abc.addLetter(new Letter("z4", true, -50, 5)); // abc.addLetter(new Letter("e", true, -10, 5)); abc.addLetter(new Letter("a0", true, -4, 1)); abc.addLetter(new Letter("a1", true, -4, 2)); abc.addLetter(new Letter("a2", true, -4, 3)); abc.addLetter(new Letter("a3", true, -4, 4)); abc.addLetter(new Letter("a4", true, -4, 5)); abc.addLetter(new Letter("a5", true, -4, 6)); abc.addLetter(new Letter("b0", true, -4, 7)); abc.addLetter(new Letter("b1", true, -4, 8)); abc.addLetter(new Letter("b2", true, -4, 9)); abc.addLetter(new Letter("b3", true, -4, 10)); abc.addLetter(new Letter("c0", true, -4, 11)); abc.addLetter(new Letter("c1", true, -4, 12)); abc.addLetter(new Letter("c2", true, -4, 13)); abc.addLetter(new Letter("d0", true, -4, 14)); abc.addLetter(new Letter("d1", true, -4, 15)); // abc.addLetter(new Letter("c2", true, -5)); Groebner g = new Groebner(); g.setDump(true); // g.addRelation(WordSum.parse("d0d1^2+d0^2d1+a1d0d1+a2d0+a3d1+a4", abc)); // g.addRelation(WordSum.parse("d1^2+2d0d1+a1d1+a2", abc)); // g.addRelation(WordSum.parse("d0^2+2d0d1+a1d0+a3", abc)); g.addRelation(WordSum.parse("ABC+BAC-CAB-CBA", abc)); g.addRelation(WordSum.parse("AC-CA", abc)); g.addRelation(WordSum.parse("CC-1", abc)); g.addRelation(WordSum.parse("AAA-a2AA-a1A", abc)); g.addRelation(WordSum.parse("BBB-b2BB-b1B-b0", abc)); // g.addRelation(WordSum.parse("CC", abc)); // g.addRelation(WordSum.parse("BAB", abc)); // g.addRelation(WordSum.parse("BAB-a0B", abc)); // g.addRelation(WordSum.parse("BCB", abc)); // g.addRelation(WordSum.parse("CBC", abc)); // g.addRelation(WordSum.parse("CDC", abc)); // g.addRelation(WordSum.parse("DCD", abc)); // g.addRelation(WordSum.parse("DAD", abc)); // g.addRelation(WordSum.parse("ADA", abc)); // g.addRelation(WordSum.parse("BCB-a1B", abc)); // g.addRelation(WordSum.parse("CA", abc)); // g.addRelation(WordSum.parse("AC", abc)); // g.addRelation(WordSum.parse("AA", abc)); // g.addRelation(WordSum.parse("AC", abc)); // g.addRelation(WordSum.parse("CA", abc)); // g.addRelation(WordSum.parse("BD", abc)); // g.addRelation(WordSum.parse("DB", abc)); // g.addRelation(WordSum.parse("BB", abc)); // g.addRelation(WordSum.parse("CC", abc)); // g.addRelation(WordSum.parse("DD", abc)); // g.addRelation(WordSum.parse("- z3 + 2a1A - b1A - a1B + a2A^2 + b2A^2 - 2c0A^2 - a2AB - a2BA + A^3B + A^2BA + ABA^2 + BA^3", abc)); // g.addRelation(WordSum.parse("D^2", abc)); // g.addRelation(WordSum.parse("A^3", abc)); // g.addRelation(WordSum.parse("B^3", abc)); // g.addRelation(WordSum.parse("C^3", abc)); // g.addRelation(WordSum.parse("D^2", abc)); // g.addRelation(WordSum.parse("a1-2", abc)); // g.addRelation(WordSum.parse("b1-1", abc)); // g.addRelation(WordSum.parse("c1-1", abc)); // g.addRelation(WordSum.parse("a0-1", abc)); // g.addRelation(WordSum.parse("b0-1", abc)); // g.addRelation(WordSum.parse("c0-1", abc)); // g.addRelation(WordSum.parse("d0-1", abc)); g.mergeRelations(); g.groebnerClosure(); // String[] gg = {"AA", "BB", "CC", "CB", "BA", "CA"}; // printBaseWords("ABC", gg, abc); // System.exit(0); Letter[] generators = Word.parseString("ABC", abc).getLetters(); Letter[] letters = Word.parseString("ABCa0a1a2b0b1b2", abc).getLetters(); // Letter[] letters = Word.parseString("ABC", abc).getLetters(); // abc.getFirstLetter("C"), abc.getFirstLetter("a0"), abc.getFirstLetter("a1"), // abc.getFirstLetter("b0"), abc.getFirstLetter("b1"), abc.getFirstLetter("c0"), // abc.getFirstLetter("c1"), abc.getFirstLetter("d0")}; int k = 0; while(true) { if(k==2) break; CenterAnalysis ca = new CenterAnalysis(generators, letters, g.getRelations()); ca.setDump(true); WordSum center = ca.findCenter(); if(center==null) break; WordSum s = new WordSum(); s.add(center, Word.ONE, Word.parseString("A", abc), Rational.ONE); s.add(center, Word.parseString("A", abc), Word.ONE, Rational.ONE.multiply(-1)); s.reduce(g.getRelations()); if(!s.isZero()) { System.out.println("Error"); return; } s.add(center, Word.ONE, Word.parseString("B", abc), Rational.ONE); s.add(center, Word.parseString("B", abc), Word.ONE, Rational.ONE.multiply(-1)); s.reduce(g.getRelations()); if(!s.isZero()) { System.out.println("Error"); return; } String newLetter = "x"+k; // if(k<2) { abc.addLetter(new Letter(newLetter, true, -3, k+1)); // } else { // abc.addLetter(new Letter(newLetter, false, 2)); // } center.add(new Word(abc.getFirstLetter(newLetter)), -1); g.addRelation(center); g.mergeRelations(); g.groebnerClosure(); Letter[] letters0 = letters; letters = new Letter[letters0.length+1]; for(int i = 0; i<letters0.length; i++) { letters[i] = letters0[i]; } letters[letters0.length] = abc.getFirstLetter(newLetter); // if(k==2) break; k++; } // abc.addLetter(new Letter("y1", true)); // abc.addLetter(new Letter("y2", true)); // abc.addLetter(new Letter("y3", true)); // abc.addLetter(new Letter("y4", true)); // abc.addLetter(new Letter("y5", true)); // abc.addLetter(new Letter("y6", true)); // abc.addLetter(new Letter("X0", true, -10, 1)); // abc.addLetter(new Letter("Y0", true, -10, 2)); // abc.addLetter(new Letter("Z0", true, -10, 3)); // abc.addLetter(new Letter("T", true, -11, 3)); // abc.addLetter(new Letter("X1", true, -9, 1)); // abc.addLetter(new Letter("Y1", true, -9, 2)); // abc.addLetter(new Letter("Z1", true, -9, 3)); // g.addRelation(WordSum.parse("X0-x1", abc)); // g.addRelation(WordSum.parse("Y0-x0", abc)); // g.addRelation(WordSum.parse("Y0^4+4X0^3", abc)); // g.addRelation(WordSum.parse("Z0-x0^2-6x2", abc)); // g.addRelation(WordSum.parse("Z0", abc)); // g.addRelation(WordSum.parse("X0+4T^4", abc)); // g.addRelation(WordSum.parse("Y0-4T^3", abc)); // g.addRelation(WordSum.parse("X0X1-1", abc)); // g.addRelation(WordSum.parse("Y0Y1-1", abc)); // g.addRelation(WordSum.parse("Z0Z1-1", abc)); // g.mergeRelations(); // g.groebnerClosure(); System.out.println("Ready for calculations, you may enter statements, type exit to exit"); BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); try { while(true) { String line = reader.readLine(); if(line.equalsIgnoreCase("exit")) { break; } WordSum res; try { res = WordSum.parse(line, abc); }catch(Error e) { System.out.println("Your input is incorrect, please try again"); continue; } res.reduce(g.getRelations()); System.out.println(res); } } catch (IOException e) { e.printStackTrace(); } /* while(true) { CenterAnalysis ca = new CenterAnalysis(generators, letters, g.getRelations()); ca.setDump(true); WordSum center = ca.findCenter(); if(center==null) break; String newLetter = "x"+k; abc.addLetter(new Letter(newLetter, true, -1, k+1)); center.add(new Word(abc.getFirstLetter(newLetter)), -1); g.addRelation(center); g.mergeRelations(); g.groebnerClosure(); Letter[] letters0 = letters; letters = new Letter[letters0.length+1]; for(int i = 0; i<letters0.length; i++) { letters[i] = letters0[i]; } letters[letters0.length] = abc.getFirstLetter(newLetter); k++; }*/ } } AAA-a2AA-a1A", abc)); g.addRelation(WordSum.parse("BBB-b2BB-b1B-b0", abc)); // g.addRelation(WordSum.parse("CC", abc)); // g.addRelation(WordSum.parse("BAB", abc)); // g.addRelation(WordSum.parse("BAB-a0B", abc)); // g.addRelation(WordSum.parse("BCB", abc)); // g.addRelation(WordSum.parse("CBC", abc)); // g.addRelation(WordSum.parse("CDC", abc)); // g.addRelation(WordSum.parse("DCD", abc)); // g.addRelation(WordSum.parse("DAD", abc)); // g.addRelatiosrc/calculus/WordSum.java 0100644 0003665 0000062 00000005771 10056446552 0016650 0 ustar 00mellit guests 0000415 0000041 package calculus; import java.util.Collection; import java.util.Iterator; import java.util.Map; import java.util.SortedMap; import algebra.linear.Sum; import algebra.numbers.Rational; import algebra.words.Alphabet; import algebra.words.Word; /** * @author Anton Mellit */ public class WordSum extends Sum { /** * Constructor for WordSum. */ public WordSum() { super(); } public void add(WordSum s, Word left, Word right, Rational r) { for(Iterator i = s.map.entrySet().iterator(); i.hasNext();) { Map.Entry entry = (Map.Entry) i.next(); Word w = ((Word) entry.getKey()).multiply(left, right); add(w, r.multiply((Rational) entry.getValue())); } } public boolean reduce(WordSum s) { Word main = (Word) s.getMainObject(); Rational k = s.getKoeff(main).invert().multiply(-1); SortedMap smallWords = map; boolean changed = false; while(!smallWords.isEmpty()) { Word w = (Word) smallWords.lastKey(); if(w.compareTo(main)<0) { break; } int pos = w.find(main, 0); if(pos>=0) { changed = true; Word[] lr = w.divide(main, pos); add(s, lr[0], lr[1], k.multiply((Rational) smallWords.get(w))); } else { } smallWords = map.headMap(w); } return changed; } /** * Relations must have main koefficient 1 */ public boolean reduce(Collection relations) { SortedMap smallWords = map; boolean changed = false; while(!smallWords.isEmpty()) { Word w = (Word) smallWords.lastKey(); for(Iterator i = relations.iterator(); i.hasNext(); ) { WordSum s = (WordSum) i.next(); Word main = (Word) s.getMainObject(); int pos = w.find(main, 0); if(pos>=0) { changed = true; Word[] lr = w.divide(main, pos); add(s, lr[0], lr[1], ((Rational) smallWords.get(w)).multiply(-1)); break; } } smallWords = map.headMap(w); } return changed; } public void parseString(String str, Alphabet abc) { setZero(); int pos = 0; while(pos<str.length()) { boolean minus = false; while(pos<str.length() && (str.charAt(pos)==' ' || str.charAt(pos)=='-' || str.charAt(pos)=='+')) { if(str.charAt(pos)=='-') { minus = true; } pos++; } if(pos==str.length()) { break; } int pos1 = pos; while(pos<str.length() && ((str.charAt(pos)>='0' && str.charAt(pos)<='9') || str.charAt(pos)=='/')) { pos++; } Rational k = Rational.ONE; if(pos1<pos) { k = Rational.parse(str.substring(pos1, pos)); } if(minus) { k = k.multiply(-1); } pos1 = pos; while(pos<str.length() && str.charAt(pos)!='+' && str.charAt(pos)!='-') { pos++; } add(Word.parseString(str.substring(pos1, pos), abc), k); } } public static WordSum parse(String str, Alphabet abc) { WordSum s = new WordSum(); s.parseString(str, abc); return s; } } src/calculus/WordSum.java~ 0100644 0003665 0000062 00000006336 07657754354 0017063 0 ustar 00mellit guests 0000415 0000041 package calculus; import java.util.Collection; import java.util.Iterator; import java.util.Map; import java.util.SortedMap; import algebra.linear.Sum; import algebra.numbers.Rational; import algebra.words.Alphabet; import algebra.words.Word; /** * @author Anton Mellit * * To change this generated comment edit the template variable "typecomment": * Window>Preferences>Java>Templates. * To enable and disable the creation of type comments go to * Window>Preferences>Java>Code Generation. */ public class WordSum extends Sum { /** * Constructor for WordSum. */ public WordSum() { super(); } public void add(WordSum s, Word left, Word right, Rational r) { for(Iterator i = s.map.entrySet().iterator(); i.hasNext();) { Map.Entry entry = (Map.Entry) i.next(); Word w = ((Word) entry.getKey()).multiply(left, right); add(w, r.multiply((Rational) entry.getValue())); } } public boolean reduce(WordSum s) { Word main = (Word) s.getMainObject(); Rational k = s.getKoeff(main).invert().multiply(-1); SortedMap smallWords = map; boolean changed = false; while(!smallWords.isEmpty()) { Word w = (Word) smallWords.lastKey(); if(w.compareTo(main)<0) { break; } int pos = w.find(main, 0); if(pos>=0) { changed = true; Word[] lr = w.divide(main, pos); add(s, lr[0], lr[1], k.multiply((Rational) smallWords.get(w))); } else { } smallWords = map.headMap(w); } return changed; } /** * Relations must have main koefficient 1 */ public boolean reduce(Collection relations) { SortedMap smallWords = map; boolean changed = false; while(!smallWords.isEmpty()) { Word w = (Word) smallWords.lastKey(); for(Iterator i = relations.iterator(); i.hasNext(); ) { WordSum s = (WordSum) i.next(); Word main = (Word) s.getMainObject(); int pos = w.find(main, 0); if(pos>=0) { changed = true; Word[] lr = w.divide(main, pos); add(s, lr[0], lr[1], ((Rational) smallWords.get(w)).multiply(-1)); break; } } smallWords = map.headMap(w); } return changed; } public void parseString(String str, Alphabet abc) { setZero(); int pos = 0; while(pos<str.length()) { boolean minus = false; while(pos<str.length() && (str.charAt(pos)==' ' || str.charAt(pos)=='-' || str.charAt(pos)=='+')) { if(str.charAt(pos)=='-') { minus = true; } pos++; } if(pos==str.length()) { break; } int pos1 = pos; while(pos<str.length() && ((str.charAt(pos)>='0' && str.charAt(pos)<='9') || str.charAt(pos)=='/')) { pos++; } Rational k = Rational.ONE; if(pos1<pos) { k = Rational.parse(str.substring(pos1, pos)); } if(minus) { k = k.multiply(-1); } pos1 = pos; while(pos<str.length() && str.charAt(pos)!='+' && str.charAt(pos)!='-') { pos++; } add(Word.parseString(str.substring(pos1, pos), abc), k); } } public static WordSum parse(String str, Alphabet abc) { WordSum s = new WordSum(); s.parseString(str, abc); return s; } } trySet().iterator(); i.hasNext();) { Map.Entry entry = (Map.Entry) i.next(); Word w = ((Word) entry.getKey()).multiply(left, right); add(w, r.multiply((Rational) entry.getValue())); } } public boolean reduce(WordSum s) { Word main = (Word) s.getMainObject(); Ratsrc/calculus/Groebner.java~ 0100644 0003665 0000062 00000012040 07746555264 0017211 0 ustar 00mellit guests 0000415 0000041 package calculus; import java.util.Collection; import java.util.Comparator; import java.util.Iterator; import java.util.LinkedList; import java.util.Set; import java.util.TreeSet; import algebra.numbers.Rational; import algebra.words.Word; /** * @author Anton Mellit * * To change this generated comment edit the template variable "typecomment": * Window>Preferences>Java>Templates. * To enable and disable the creation of type comments go to * Window>Preferences>Java>Code Generation. */ class SplitComp implements Comparator { /** * @see java.util.Comparator#compare(Object, Object) */ public int compare(Object o1, Object o2) { Word.Split s1 = (Word.Split) o1; Word.Split s2 = (Word.Split) o2; int c = s1.left.compareTo(s2.left); if(c!=0) return c; c = s1.center.compareTo(s2.center); if(c!=0) return c; c = s1.right.compareTo(s2.right); return c; } } class Composition { public WordSum s1; public WordSum s2; public Word.Split split; } public class Groebner { protected Collection relations; protected Set splitsUsed; protected Collection newRelations; protected Collection newCompositions; protected boolean dump; public Groebner() { relations = new LinkedList(); splitsUsed = new TreeSet(new SplitComp()); newRelations = new LinkedList(); newCompositions = new LinkedList(); } /** * Sets the dump. * @param dump The dump to set */ public void setDump(boolean dump) { this.dump = dump; } public void addRelation(WordSum rel) { rel.reduce(relations); if(!rel.isZero()) { rel.normalize(); newRelations.add(rel); if(dump) { // System.out.println("Added new relation "+rel); } } } protected boolean pairwiseReduce() { if(dump) { System.out.println("Pairwise reduce ("+relations.size()+" relations)"); } boolean changed = false; int k = 0; for(Iterator i1 = relations.iterator(); i1.hasNext(); ) { k++; WordSum s1 = (WordSum) i1.next(); if(s1.isZero()) { i1.remove(); changed = true; } else { for(Iterator i2 = relations.iterator(); i2.hasNext(); ) { WordSum s2 = (WordSum) i2.next(); if(s1!=s2) { if(s2.reduce(s1)) { s2.normalize(); changed = true; } } } } if(k%10==0) { System.out.println("Ready: "+k); } } return changed; } protected void fullReduce() { if(dump) { System.out.println("Reducing all relations"); } while(pairwiseReduce()); } public void dumpStatus() { if(dump) { System.out.println("Have "+relations.size()+" relations:"); for(Iterator i1 = relations.iterator(); i1.hasNext(); ) { WordSum s1 = (WordSum) i1.next(); System.out.println(s1.toString(true)); } } } public void mergeRelations() { relations.addAll(newRelations); newRelations.clear(); fullReduce(); dumpStatus(); } protected void makeCompositions() { for(Iterator i1 = relations.iterator(); i1.hasNext(); ) { WordSum s1 = (WordSum) i1.next(); Word m1 = (Word) s1.getMainObject(); for(Iterator i2 = relations.iterator(); i2.hasNext(); ) { WordSum s2 = (WordSum) i2.next(); Word m2 = (Word) s2.getMainObject(); Collection splits = m1.getAllSplits(m2); for(Iterator i3 = splits.iterator(); i3.hasNext(); ) { Word.Split split = (Word.Split) i3.next(); if(!splitsUsed.contains(split)) { splitsUsed.add(split); addComposition(s1, s2, split); } } } } } protected void addComposition(WordSum s1, WordSum s2, Word.Split split) { if(dump) { System.out.println("Scheduled composition "+splitToString(split)); } Composition c = new Composition(); c.s1 = s1; c.s2 = s2; c.split = split; newCompositions.add(c); } protected String splitToString(Word.Split split) { return split.left.toString()+"|"+split.center+"|"+split.right; } protected void mergeCompositions() { int j = 0; for(Iterator i = newCompositions.iterator(); i.hasNext(); ) { mergeComposition((Composition) i.next(), j); j++; } newCompositions.clear(); } protected void mergeComposition(Composition c, int i) { if(dump) { System.out.println("Making composition "+splitToString(c.split)+" ("+i+"/"+newCompositions.size()+")"); } WordSum s = new WordSum(); s.add(c.s1, Word.ONE, c.split.right, Rational.valueOf(1)); s.add(c.s2, c.split.left, Word.ONE, Rational.valueOf(-1)); addRelation(s); } public boolean fullCompose() { makeCompositions(); boolean changed = !newCompositions.isEmpty(); mergeCompositions(); return changed; } public void groebnerClosure() { boolean changed; do { changed = fullCompose(); mergeRelations(); } while(changed); } public Collection getRelations() { return relations; } public void dump() { System.out.println("Relations:"); for (Iterator iter = relations.iterator(); iter.hasNext();) { WordSum ws = (WordSum) iter.next(); System.out.println(ws); } } } src/calculus/CenterAnalysis.java~ 0100644 0003665 0000062 00000007370 10056447115 0020363 0 ustar 00mellit guests 0000415 0000041 package calculus; import java.util.Collection; import java.util.Iterator; import java.util.Map; import java.util.Set; import java.util.TreeMap; import java.util.TreeSet; import algebra.linear.Sum; import algebra.numbers.Rational; import algebra.words.Letter; import algebra.words.Word; /** * @author Anton Mellit */ class Commutator { public WordSum x; public Sum values; } public class CenterAnalysis { protected Map comms; protected Letter[] letters; protected Letter[] generators; protected Set wordsToProcess; protected Set nextWords; protected Collection groebnerBase; protected boolean dump; protected int length; public CenterAnalysis(Letter[] generators, Letter[] letters, Collection groebnerBase) { comms = new TreeMap(); this.letters = letters; this.generators = generators; wordsToProcess = new TreeSet(); nextWords = new TreeSet(); this.groebnerBase = groebnerBase; length = 0; } /** * Sets the dump. * @param dump The dump to set */ public void setDump(boolean dump) { this.dump = dump; } protected void init() { for(int i = 0; i<letters.length; i++) { if(!letters[i].isCentral()) { nextWords.add(new Word(letters[i])); } } length = 1; } protected WordSum process() { if(dump) { System.out.println("Processing words with length "+length+" ("+nextWords.size()+" words)"); } wordsToProcess.clear(); wordsToProcess.addAll(nextWords); nextWords.clear(); for(Iterator i = wordsToProcess.iterator(); i.hasNext(); ) { Word w = (Word) i.next(); if(isBaseWord(w)) { // System.out.println(w); addWords(w); Commutator comm = addCommutator(w); if(comm.values.isZero()) { if(dump) { System.out.println("Central element found: "+comm.x); } return comm.x; } } } length++; return null; } public WordSum findCenter() { init(); WordSum answer = null; while(answer==null && !nextWords.isEmpty() && length<31) { answer = process(); } return answer; } protected boolean isBaseWord(Word w) { for(Iterator i = groebnerBase.iterator(); i.hasNext(); ) { WordSum s = (WordSum) i.next(); if(w.find((Word) s.getMainObject(), 0)>=0) { return false; } } return true; } protected void addWords(Word w) { for(int i = 0; i<letters.length; i++) { // if(length<9 || (!letters[i].isCentral()&&!w.getLetters()[0].isCentral())) { nextWords.add(w.multiply(new Word(letters[i]), Word.ONE)); // } } } protected Commutator addCommutator(Word w) { Commutator comm = new Commutator(); comm.values = new Sum(); for(int i = 0; i<generators.length; i++) { addCommutator(comm.values, w, new Word(generators[i])); } comm.x = new WordSum(); comm.x.add(w); if(!comm.values.isZero()) { reduce(comm); } if(!comm.values.isZero()) { comms.put(comm.values.getMainObject(), comm); } return comm; } protected void addCommutator(Sum s, Word w, Word x) { WordSum c = new WordSum(); c.add(w.multiply(x, Word.ONE)); c.add(w.multiply(Word.ONE, x), -1); c.reduce(groebnerBase); for(Iterator i = c.getObjects().iterator(); i.hasNext(); ) { Object o = i.next(); s.add(x.toString()+": "+o, c.getKoeff(o)); } } protected void reduce(Commutator comm) { boolean finished = false; do { Object main = comm.values.getMainObject(); Commutator mod = (Commutator) comms.get(main); if(mod!=null) { Rational k = comm.values.getKoeff(main).divide( mod.values.getKoeff(mod.values.getMainObject())).multiply(-1); comm.values.add(mod.values, k); comm.x.add(mod.x, k); } else { finished = true; } } while(!finished && !comm.values.isZero()); } } } protected WordSum process() { if(dump) { System.out.println("Processing words with length "+length+" ("+nextWords.size()+" words)"); } wordsToProcess.clear(); wordsToProcess.addAll(nextWords); nextWords.clear(); for(Iterator i = wordsrc/util/ 0040755 0003665 0000062 00000000000 10056447713 0013540 5 ustar 00mellit guests 0000415 0000041 src/util/GroebnerBasis.java 0100644 0003665 0000062 00000005476 10056447713 0017141 0 ustar 00mellit guests 0000415 0000041 package util; import java.io.*; import algebra.words.Letter; import algebra.words.Word; import calculus.CenterAnalysis; import calculus.WordSum; /** * @author Anton Mellit */ public class GroebnerBasis { public static void main(String[] args) { // args = new String[]{"groebner", "test.in", "test.out", "t"}; if(args.length<2) { System.out.println("Please, specify command followed by setting file"); System.out.println("Possible commands are: groebner, center, calculator"); return; } Setting set = new Setting(); try { set.load(args[1]); set.dump(); String command = args[0]; set.getRelations().setDump(true); if(command.equalsIgnoreCase("center")) { if(args.length<4) { System.out.println( "Please, specify output file and letter which will be assigned result value"); return; } String letterName = args[3]; Letter centralLetter = set.getAbc().getFirstLetter(letterName); if(centralLetter==null) { System.out.println("Error: Letter "+letterName+" is not in the alphabet"); return; } CenterAnalysis ca = new CenterAnalysis( set.getGenerators(), set.getAbc().getLetters(), set.getRelations().getRelations()); ca.setDump(true); WordSum ws = ca.findCenter(); if(ws==null) { System.out.println("Center not found"); } else { System.out.println("Central element found and is :"); System.out.println(ws); ws.add(new Word(centralLetter), -1); set.getRelations().addRelation(ws); set.getRelations().mergeRelations(); } set.save(args[2]); } else if(command.equalsIgnoreCase("groebner")) { if(args.length<3) { System.out.println("Please, specify output file"); return; } set.getRelations().setDump(true); set.getRelations().groebnerClosure(); set.save(args[2]); } else if(command.equalsIgnoreCase("calculator")) { System.out.println("Ready for calculations, you may enter statements, type exit to exit"); BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); try { while(true) { String line = reader.readLine(); if(line.equalsIgnoreCase("exit")) { break; } WordSum res; try { res = WordSum.parse(line, set.getAbc()); res.reduce(set.getRelations().getRelations()); }catch(Exception e) { System.out.println("Your input is incorrect, please try again"); continue; } System.out.println(res); } } catch (IOException e) { e.printStackTrace(); } } else { System.out.println("Command "+command+" not supported"); return; } } catch(IOException e) { System.out.println(e.getLocalizedMessage()); } } } src/util/Setting.java 0100644 0003665 0000062 00000006667 10056447242 0016031 0 ustar 00mellit guests 0000415 0000041 package util; import java.io.*; import java.util.Iterator; import java.util.List; import java.util.Vector; import algebra.words.Alphabet; import algebra.words.Letter; import calculus.Groebner; import calculus.WordSum; /** * @author Anton Mellit */ public class Setting { private Alphabet abc; private Groebner relations; private Vector generators; public Setting() { abc = new Alphabet(); relations = new Groebner(); generators = new Vector(); } public void save(String file) throws IOException { PrintStream ps = new PrintStream(new FileOutputStream(file)); ps.println("[Alphabet]"); Letter[] letters = abc.getLetters(); for (int j = 0; j < letters.length; j++) { //sort by index for (int i = 0; i < letters.length-1; i++) { if(letters[i].getIndex()>letters[i+1].getIndex()) { Letter l = letters[i]; letters[i] = letters[i+1]; letters[i+1] = l; } } } for (int i = 0; i < letters.length; i++) { ps.println("weight "+letters[i].getLevel()+ (letters[i].isCentral()? " central ":" noncentral ")+ letters[i].getName()); } ps.println("[Generators]"); for (Iterator iter = generators.iterator(); iter.hasNext();) { Letter l = (Letter) iter.next(); ps.println(l); } ps.println("[Relations]"); for (Iterator iter = relations.getRelations().iterator(); iter.hasNext();) { WordSum ws = (WordSum) iter.next(); ps.println("\""+ws+"\""); } ps.close(); } public void load(String file) throws IOException { InputStream is; StreamTokenizer s= new StreamTokenizer(new InputStreamReader(is=new FileInputStream(file))); s.parseNumbers(); s.slashSlashComments(true); String section = ""; s.eolIsSignificant(true); boolean commuting = false; int weight = 0; int k = 0; while(s.nextToken()!=s.TT_EOF) { if(s.ttype==s.TT_EOL) continue; if(s.ttype=='[') { if(s.nextToken()==s.TT_WORD) { section = s.sval; s.nextToken(); continue; } } if(section.equalsIgnoreCase("Alphabet")) { if(s.ttype==s.TT_WORD) { if(s.sval.equalsIgnoreCase("Central")) { commuting = true; } else if(s.sval.equalsIgnoreCase("Noncentral")) { commuting = false; } else if(s.sval.equalsIgnoreCase("Weight")) { if(s.nextToken()==s.TT_NUMBER) { weight = (int) s.nval; } else { s.pushBack(); } } else { k++; Letter l = new Letter(s.sval, commuting, weight, k); abc.addLetter(l); } } } else if(section.equalsIgnoreCase("Generators")) { if(s.ttype==s.TT_WORD) { generators.add(abc.getFirstLetter(s.sval)); } } else if(section.equalsIgnoreCase("Relations")) { if(s.ttype=='"') { relations.addRelation(WordSum.parse(s.sval, abc)); } } } is.close(); relations.mergeRelations(); } /** * Returns the abc. * @return Alphabet */ public Alphabet getAbc() { return abc; } /** * Returns the relations. * @return Groebner */ public Groebner getRelations() { return relations; } public Letter[] getGenerators() { Letter[] res = new Letter[generators.size()]; return (Letter[]) generators.toArray(res); } public void dump() { abc.dump(); System.out.print("Generators:"); Letter[] gens = getGenerators(); for (int i = 0; i < gens.length; i++) { System.out.print(" "+gens[i]); } System.out.println(); relations.dump(); } } src/util/Setting.java~ 0100644 0003665 0000062 00000007222 07746561540 0016225 0 ustar 00mellit guests 0000415 0000041 package util; import java.io.*; import java.util.Iterator; import java.util.List; import java.util.Vector; import algebra.words.Alphabet; import algebra.words.Letter; import calculus.Groebner; import calculus.WordSum; /** * @author Anton Mellit * * To change this generated comment edit the template variable "typecomment": * Window>Preferences>Java>Templates. * To enable and disable the creation of type comments go to * Window>Preferences>Java>Code Generation. */ public class Setting { private Alphabet abc; private Groebner relations; private Vector generators; public Setting() { abc = new Alphabet(); relations = new Groebner(); generators = new Vector(); } public void save(String file) throws IOException { PrintStream ps = new PrintStream(new FileOutputStream(file)); ps.println("[Alphabet]"); Letter[] letters = abc.getLetters(); for (int j = 0; j < letters.length; j++) { //sort by index for (int i = 0; i < letters.length-1; i++) { if(letters[i].getIndex()>letters[i+1].getIndex()) { Letter l = letters[i]; letters[i] = letters[i+1]; letters[i+1] = l; } } } for (int i = 0; i < letters.length; i++) { ps.println("weight "+letters[i].getLevel()+(letters[i].isCentral()? " central ":" noncentral ")+ letters[i].getName()); } ps.println("[Generators]"); for (Iterator iter = generators.iterator(); iter.hasNext();) { Letter l = (Letter) iter.next(); ps.println(l); } ps.println("[Relations]"); for (Iterator iter = relations.getRelations().iterator(); iter.hasNext();) { WordSum ws = (WordSum) iter.next(); ps.println("\""+ws+"\""); } ps.close(); } public void load(String file) throws IOException { InputStream is; StreamTokenizer s= new StreamTokenizer(new InputStreamReader(is=new FileInputStream(file))); s.parseNumbers(); s.slashSlashComments(true); String section = ""; s.eolIsSignificant(true); boolean commuting = false; int weight = 0; int k = 0; while(s.nextToken()!=s.TT_EOF) { if(s.ttype==s.TT_EOL) continue; if(s.ttype=='[') { if(s.nextToken()==s.TT_WORD) { section = s.sval; s.nextToken(); continue; } } if(section.equalsIgnoreCase("Alphabet")) { if(s.ttype==s.TT_WORD) { if(s.sval.equalsIgnoreCase("Central")) { commuting = true; } else if(s.sval.equalsIgnoreCase("Noncentral")) { commuting = false; } else if(s.sval.equalsIgnoreCase("Weight")) { if(s.nextToken()==s.TT_NUMBER) { weight = (int) s.nval; } else { s.pushBack(); } } else { k++; Letter l = new Letter(s.sval, commuting, weight, k); abc.addLetter(l); } } } else if(section.equalsIgnoreCase("Generators")) { if(s.ttype==s.TT_WORD) { generators.add(abc.getFirstLetter(s.sval)); } } else if(section.equalsIgnoreCase("Relations")) { if(s.ttype=='"') { relations.addRelation(WordSum.parse(s.sval, abc)); } } } is.close(); relations.mergeRelations(); } /** * Returns the abc. * @return Alphabet */ public Alphabet getAbc() { return abc; } /** * Returns the relations. * @return Groebner */ public Groebner getRelations() { return relations; } public Letter[] getGenerators() { Letter[] res = new Letter[generators.size()]; return (Letter[]) generators.toArray(res); } public void dump() { abc.dump(); System.out.print("Generators:"); Letter[] gens = getGenerators(); for (int i = 0; i < gens.length; i++) { System.out.print(" "+gens[i]); } System.out.println(); relations.dump(); } } src/util/GroebnerBasis.java~ 0100644 0003665 0000062 00000005744 07746562214 0017343 0 ustar 00mellit guests 0000415 0000041 package util; import java.io.*; import algebra.words.Letter; import algebra.words.Word; import calculus.CenterAnalysis; import calculus.WordSum; /** * @author Anton Mellit * * To change this generated comment edit the template variable "typecomment": * Window>Preferences>Java>Templates. * To enable and disable the creation of type comments go to * Window>Preferences>Java>Code Generation. */ public class GroebnerBasis { public static void main(String[] args) { // args = new String[]{"groebner", "test.in", "test.out", "t"}; if(args.length<2) { System.out.println("Please, specify command followed by setting file"); System.out.println("Possible commands are: groebner, center, calculator"); return; } Setting set = new Setting(); try { set.load(args[1]); set.dump(); String command = args[0]; set.getRelations().setDump(true); if(command.equalsIgnoreCase("center")) { if(args.length<4) { System.out.println("Please, specify output file and letter which will be assigned result value"); return; } String letterName = args[3]; Letter centralLetter = set.getAbc().getFirstLetter(letterName); if(centralLetter==null) { System.out.println("Error: Letter "+letterName+" is not in the alphabet"); return; } CenterAnalysis ca = new CenterAnalysis(set.getGenerators(), set.getAbc().getLetters(), set.getRelations().getRelations()); ca.setDump(true); WordSum ws = ca.findCenter(); if(ws==null) { System.out.println("Center not found"); } else { System.out.println("Central element found and is :"); System.out.println(ws); ws.add(new Word(centralLetter), -1); set.getRelations().addRelation(ws); set.getRelations().mergeRelations(); } set.save(args[2]); } else if(command.equalsIgnoreCase("groebner")) { if(args.length<3) { System.out.println("Please, specify output file"); return; } set.getRelations().setDump(true); set.getRelations().groebnerClosure(); set.save(args[2]); } else if(command.equalsIgnoreCase("calculator")) { System.out.println("Ready for calculations, you may enter statements, type exit to exit"); BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); try { while(true) { String line = reader.readLine(); if(line.equalsIgnoreCase("exit")) { break; } WordSum res; try { res = WordSum.parse(line, set.getAbc()); res.reduce(set.getRelations().getRelations()); }catch(Exception e) { System.out.println("Your input is incorrect, please try again"); continue; } System.out.println(res); } } catch (IOException e) { e.printStackTrace(); } } else { System.out.println("Command "+command+" not supported"); return; } } catch(IOException e) { System.out.println(e.getLocalizedMessage()); } } }