Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs	(revision 11902)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs	(revision 11902)
@@ -0,0 +1,275 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  // helper to create canonical forms of expressions
+  // TODO: change symbolicregressionpoly10problem to use this class
+  // this does not support expressions with constants (in transformations we assume constant opt is used)
+  // (e.g. we transform all negative signs to + because it is assumed a negative constant can be produced for the term)
+  public class ExpressionExtender {
+
+    // supports the grammar
+    // G(E):
+    //     E -> V | V+E | V-E | V*E | V%E | (E) 
+    //     V -> <variables>
+    //     ";
+
+    // transformations: 
+    // - transform c*b*a to a*b*c (lexicographic ordering for factors, cached)
+    // - transfrom - to + (assumed optimized constants for terms)
+
+
+    // most-recently-used caching (with limited capacity) for canonical representations
+    MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
+    public string CanonicalRepresentation(string phrase) {
+      int pos = 0;
+      return CanonicalExpr(phrase, ref pos);
+    }
+
+    private Expr CanonicalExpr(string phrase, ref int pos) {
+      var terms = new List<Term>();
+      terms.Add(CanonicalTerm(phrase, ref pos));
+      var curSy = phrase[pos];
+      while (curSy == '+' || curSy == '-' || curSy == '^') {
+        if (curSy == '+') {
+          pos++;
+          terms.Add(CanonicalTerm(phrase, ref pos));
+        } else if (curSy == '-') {
+          pos++;
+          terms.Add(CanonicalTerm(phrase, ref pos)); // minus is the same as plus assuming constant opt
+        } else {
+          pos++;
+          throw new NotImplementedException();
+          // var e = Expr(variables, constants);
+          // r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
+        }
+        curSy = phrase[pos];
+      }
+
+      // at this point we might have multiple constants in the list of terms but we only need one of them
+      var firstConstant = terms.OfType<Variable>().FirstOrDefault(); // if a term is only a variable then it must be a constant (otherwise (for real variables) it would be a product of two constants)
+      if (firstConstant == null) {
+        // no constant found => add a constant offset for each full expression
+        var offset = new Variable();
+        constants.Add(offset);
+        terms.Add(offset);
+      } else {
+        // there is already a constant => remove all others if there are more
+        var otherConsts = terms.OfType<Variable>().Where(t => t != firstConstant).ToArray();
+        foreach (var otherConst in otherConsts) {
+          terms.Remove(otherConst);
+          constants.Remove(otherConst);
+        }
+      }
+      return TermBuilder.Sum(terms);
+    }
+
+    private Term CanonicalTerm(string phrase, ref int pos) {
+      var factors = new List<Factor>();
+      var invFactors = new List<Factor>();
+      var f = CanonicalFact(phrase, ref pos);
+      if (f != null) factors.Add(f);
+      var curSy = phrase[pos];
+      while (curSy == '*' || curSy == '%') {
+        if (curSy == '*') {
+          pos++;
+          f = CanonicalFact(phrase, ref pos); // fact might return string.Empty (for constants)
+          if (f != null) factors.Add(f);
+        } else {
+          pos++;
+          f = CanonicalFact(phrase, ref pos);
+          if (f != null) invFactors.Add(f);
+        }
+        curSy = phrase[pos];
+      }
+
+      // cancel factors if they are contained in factors and invFactors
+      foreach (var cancelledF in factors.Intersect(invFactors).ToArray()) {
+        factors.Remove(cancelledF);
+        invFactors.Remove(cancelledF);
+      }
+      // at this point factors and invFactors might be empty
+      if (factors.Count == 0 && invFactors.Count == 0) throw new NotImplementedException();
+
+      if(factors.Count == 1)
+      // extend factors if they are composed of terms
+      // this means that we return a list of terms instead of one single term
+      // at this point factors can only be a list of additive terms
+      var extendedFactors = new List<Factor>();
+
+      // order factors (bysize then lexicographically)
+    }
+
+    private Factor CanonicalFact(string phrase, ref int pos) {
+      var curSy = phrase[pos];
+      if (curSy == '!') {
+        throw new NotSupportedException();
+      } else if (curSy == '(') {
+        pos++;
+        Expr r = CanonicalExpr(phrase, ref pos);
+        if (phrase[pos] != ')') throw new ArgumentException();
+        pos++;
+        if (r.Kind == ExprKind.SimpleExpr)
+          return new Factor(r.Term);
+        else
+          return new Factor(r.Terms); // a composite factor
+      } else if (curSy >= 'a' && curSy <= 'z') {
+        pos++;
+        return new Factor(curSy.ToString());
+        //       } else if (curSy >= '0' && curSy <= '9') {
+      } else throw new ArgumentException("found symbol " + curSy);
+    }
+
+    #region factor
+    private enum FactorKind { SimpleFactor, Expr }
+    private class Factor {
+      public readonly FactorKind Kind;
+      public readonly string Value; // only set for Kind == SimpleFactor
+      public readonly IEnumerable<string> Values; // only set for Kind == Expr 
+
+      public Factor(string f) {
+        this.Kind = FactorKind.SimpleFactor;
+        this.Value = f;
+      }
+      public Factor(IEnumerable<string> factorTerms) {
+        this.Kind = FactorKind.Expr;
+        this.Values = factorTerms;
+      }
+
+      public override string ToString() {
+        if (Kind == FactorKind.SimpleFactor) return Value;
+        else return string.Join("+", Values);
+      }
+      public override bool Equals(object obj) {
+        var other = obj as Factor;
+        if (other == null) return false;
+        if (other.Kind != this.Kind) return false;
+        if (Kind == FactorKind.SimpleFactor) return this.Value == other.Value;
+        if (this.Values.Count() != other.Values.Count()) return false;
+        if (this.Values.Zip(other.Values, Tuple.Create).All(t => t.Item1 == t.Item2)) return true;
+        return false;
+      }
+      public override int GetHashCode() {
+        var h = 31415;
+        if (Value != null) h ^= Value.GetHashCode();
+        foreach (var v in Values) {
+          h ^= v.GetHashCode();
+        }
+        return h;
+      }
+    }
+    #endregion
+    #region term
+    private enum TermKind { SimpleTerm, Term }
+    private class Term {
+      public readonly TermKind Kind;
+      public readonly Factor Factor; // only set for Kind == Simple
+      public readonly IEnumerable<Factor> Factors;
+
+      public Term(Factor f) {
+        this.Kind = TermKind.SimpleTerm;
+        this.Factor = f;
+      }
+      public Term(IEnumerable<Factor> factors) {
+        this.Kind = TermKind.Term;
+        this.Factors = factors;
+      }
+
+      public override string ToString() {
+        if (Kind == TermKind.SimpleTerm) return Factor.ToString();
+        else return string.Join("+", Factors);
+      }
+      public override bool Equals(object obj) {
+        var other = obj as Term;
+        if (other == null) return false;
+        if (other.Kind != this.Kind) return false;
+        if (Kind == TermKind.SimpleTerm) return this.Factor == other.Factor;
+        if (this.Factors.Count() != other.Factors.Count()) return false;
+        if (this.Factors.Zip(other.Factors, Tuple.Create).All(t => t.Item1 == t.Item2)) return true;
+        return false;
+      }
+      public override int GetHashCode() {
+        var h = 31415;
+        if (Factor != null) h ^= Factor.GetHashCode();
+        foreach (var t in Factors) {
+          h ^= t.GetHashCode();
+        }
+        return h;
+      }
+    }
+    #endregion
+    #region expr
+    private enum ExprKind { SimpleExpr, Expr }
+    private class Expr {
+      public readonly ExprKind Kind;
+      public readonly string Term; // only set for Kind == SimpleExpr
+      public readonly IEnumerable<string> Terms; // only set for Kind == Expr 
+
+      public Expr(string f) {
+        this.Kind = ExprKind.SimpleExpr;
+        this.Term = f;
+      }
+      public Expr(IEnumerable<string> exprTerms) {
+        this.Kind = ExprKind.Expr;
+        this.Terms = exprTerms;
+      }
+
+      public override string ToString() {
+        if (Kind == ExprKind.SimpleExpr) return Term;
+        else return string.Join("+", Terms);
+      }
+      public override bool Equals(object obj) {
+        var other = obj as Expr;
+        if (other == null) return false;
+        if (other.Kind != this.Kind) return false;
+        if (Kind == ExprKind.SimpleExpr) return this.Term == other.Term;
+        if (this.Terms.Count() != other.Terms.Count()) return false;
+        if (this.Terms.Zip(other.Terms, Tuple.Create).All(t => t.Item1 == t.Item2)) return true;
+        return false;
+      }
+      public override int GetHashCode() {
+        var h = 31415;
+        if (Term != null) h ^= Term.GetHashCode();
+        foreach (var t in Terms) {
+          h ^= t.GetHashCode();
+        }
+        return h;
+      }
+    }
+    #endregion
+    // private enum TermKind { }
+    // private class Term {
+    //   public TermKind Kind;
+    //   public string FirstFactor; // always set
+    //   public IEnumerable<string> RemainingFactors; // only set for Kind == Expr 
+    // }
+
+    // cache the canonical form of terms for performance reasons
+    private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
+    private string CanonicalTerm(string term) {
+      string canonicalTerm;
+      if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm)) {
+        // add
+        var chars = term.ToCharArray();
+        Array.Sort(chars);
+        var sb = new StringBuilder(chars.Length);
+        // we want to have the up-case characters last
+        for (int i = chars.Length - 1; i > 0; i--) {
+          if (chars[i] != '*') {
+            sb.Append(chars[i]);
+            if (chars[i - 1] != '*') sb.Append('*');
+          }
+        }
+        if (chars[0] != '*') sb.Append(chars[0]); // last term
+        canonicalTerm = sb.ToString();
+        canonicalTermDictionary.Add(term, canonicalTerm);
+      }
+      return canonicalTerm;
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/HeuristicLab.Common.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/HeuristicLab.Common.csproj	(revision 11896)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/HeuristicLab.Common.csproj	(revision 11902)
@@ -36,4 +36,5 @@
   <ItemGroup>
     <Compile Include="ConsoleEx.cs" />
+    <Compile Include="ExpressionExtender.cs" />
     <Compile Include="Extensions.cs" />
     <Compile Include="MostRecentlyUsedCache.cs" />
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs	(revision 11896)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs	(revision 11902)
@@ -19,4 +19,5 @@
   public class SymbolicRegressionProblem : ISymbolicExpressionTreeProblem {
 
+    // C represents Koza-style ERC (the symbol is the index of the ERC), the values are initialized below
     private const string grammarString = @"
         G(E):
@@ -25,5 +26,11 @@
         V -> <variables>
         ";
-    // C represents Koza-style ERC (the symbol is the index of the ERC), the values are initialized below
+
+    // when using constant opt optimal constants are generated in the evaluation step so we don't need them in the grammar
+    private const string grammarConstOptString = @"
+        G(E):
+        E -> V | V+E | V*E | V%E | (E) 
+        V -> <variables>
+        ";
 
     // S .. Sum (+), N .. Neg. sum (-), P .. Product (*), D .. Division (%)
@@ -38,4 +45,12 @@
         V -> <variables>
         ";
+    private const string treeGrammarConstOptString = @"
+        G(E):
+        E -> V | S | P | D 
+        S -> EE | EEE
+        P -> EE | EEE
+        D -> EE
+        V -> <variables>
+        ";
 
     // when we use constants optimization we can completely ignore all constants by a simple strategy:
@@ -51,9 +66,11 @@
     private readonly int d;
     private readonly double[] erc;
-
-
-    public SymbolicRegressionProblem(Random random, string partOfName) {
+    private readonly bool useConstantOpt;
+
+
+    public SymbolicRegressionProblem(Random random, string partOfName, bool useConstantOpt = true) {
       var instanceProvider = new RegressionRealWorldInstanceProvider();
       var dds = instanceProvider.GetDataDescriptors().OfType<RegressionDataDescriptor>();
+      this.useConstantOpt = useConstantOpt;
 
       var problemData = instanceProvider.LoadData(dds.Single(ds => ds.Name.Contains(partOfName)));
@@ -78,6 +95,11 @@
       char firstVar = 'a';
       char lastVar = Convert.ToChar(Convert.ToByte('a') + d - 1);
-      this.grammar = new Grammar(grammarString.Replace("<variables>", firstVar + " .. " + lastVar));
-      this.TreeBasedGPGrammar = new Grammar(treeGrammarString.Replace("<variables>", firstVar + " .. " + lastVar));
+      if (!useConstantOpt) {
+        this.grammar = new Grammar(grammarString.Replace("<variables>", firstVar + " .. " + lastVar));
+        this.TreeBasedGPGrammar = new Grammar(treeGrammarString.Replace("<variables>", firstVar + " .. " + lastVar));
+      } else {
+        this.grammar = new Grammar(grammarConstOptString.Replace("<variables>", firstVar + " .. " + lastVar));
+        this.TreeBasedGPGrammar = new Grammar(treeGrammarConstOptString.Replace("<variables>", firstVar + " .. " + lastVar));
+      }
     }
 
@@ -93,5 +115,9 @@
 
     public double Evaluate(string sentence) {
-      return OptimizeConstantsAndEvaluate(sentence);
+      if (useConstantOpt)
+        return OptimizeConstantsAndEvaluate(sentence);
+      else {
+        return SimpleEvaluate(sentence);
+      }
     }
 
@@ -107,11 +133,13 @@
 
     public string CanonicalRepresentation(string phrase) {
-      return phrase;
-      //var terms = phrase.Split('+');
-      //return string.Join("+", terms.Select(term => string.Join("", term.Replace("*", "").OrderBy(ch => ch)))
-      //  .OrderBy(term => term));
+      throw new NotImplementedException();
     }
 
     public IEnumerable<Feature> GetFeatures(string phrase) {
+      // first generate canonical expression (which must not contain ())
+      // recursively split into expressions
+      // for each expression split into terms
+      // for each term order factors to canonical // ../E = * 1/E
+      var canonical = CanonicalRepresentation(phrase);
       throw new NotImplementedException();
     }
@@ -212,5 +240,5 @@
         }
         // nonterminal
-        if (op == "+" || op == "-") sb.Append("(");
+        if (treeNode.SubtreeCount > 1) sb.Append("(");
         TreeToSentence(treeNode.Subtrees.First(), sb);
         foreach (var subTree in treeNode.Subtrees.Skip(1)) {
@@ -218,5 +246,5 @@
           TreeToSentence(subTree, sb);
         }
-        if (op == "+" || op == "-") sb.Append(")");
+        if (treeNode.SubtreeCount > 1) sb.Append(")");
       }
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/Test/Test.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/Test/Test.csproj	(revision 11896)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/Test/Test.csproj	(revision 11902)
@@ -69,4 +69,5 @@
   </Choose>
   <ItemGroup>
+    <Compile Include="TestCanonicalExpressions.cs" />
     <Compile Include="TestSymbRegInstances.cs" />
     <Compile Include="TestSequence.cs" />
@@ -88,4 +89,8 @@
       <Project>{eea07488-1a51-412a-a52c-53b754a628b3}</Project>
       <Name>HeuristicLab.Algorithms.GrammaticalOptimization</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Common\HeuristicLab.Common.csproj">
+      <Project>{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}</Project>
+      <Name>HeuristicLab.Common</Name>
     </ProjectReference>
     <ProjectReference Include="..\HeuristicLab.Distributions\HeuristicLab.Distributions.csproj">
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs	(revision 11902)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs	(revision 11902)
@@ -0,0 +1,89 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Algorithms.Bandits;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
+  [TestClass]
+  public class TestCanonicalExpressions {
+    [TestMethod]
+    public void TestFactorReordering() {
+      var extender = new ExpressionExtender();
+      Assert.AreEqual("a*b", extender.CanonicalRepresentation("b*a"));
+      Assert.AreEqual("a*b*c", extender.CanonicalRepresentation("b*a*c"));
+      Assert.AreEqual("a*b*E", extender.CanonicalRepresentation("b*a*E"));
+    }
+
+    [TestMethod]
+    public void TestDuplicateTerms() {
+      var extender = new ExpressionExtender();
+      Assert.AreEqual("a", extender.CanonicalRepresentation("a+a"));
+      Assert.AreEqual("a+b", extender.CanonicalRepresentation("b+a+b"));
+      Assert.AreEqual("a+b", extender.CanonicalRepresentation("b+a-b")); // even though b-b canceles should keep this as we might find a non-zero factor for b
+    }
+
+    [TestMethod]
+    public void TestSimpleTermReordering() {
+      var extender = new ExpressionExtender();
+      Assert.AreEqual("a+b", extender.CanonicalRepresentation("b+a"));
+      Assert.AreEqual("a+b+c", extender.CanonicalRepresentation("b+a+c"));
+      Assert.AreEqual("a+b+E", extender.CanonicalRepresentation("b+a+E"));
+    }
+
+    [TestMethod]
+    public void TestCombinedTermReordering() {
+      var extender = new ExpressionExtender();
+      Assert.AreEqual("a+b+a*b+E", extender.CanonicalRepresentation("b*a+b+a+E"));
+      Assert.AreEqual("a+b+b*c+E", extender.CanonicalRepresentation("c*b+b+a+E"));
+      Assert.AreEqual("a+b+b*c+a*b*c+E", extender.CanonicalRepresentation("c*b+b*a*c+b+a+E"));
+    }
+    [TestMethod]
+    public void TestNegativeAndReorderTerms() {
+      var extender = new ExpressionExtender();
+      // when using constant opt the negative sign is not necessary because a negative factor can be produced
+      Assert.AreEqual("a+b", extender.CanonicalRepresentation("b-a"));
+      Assert.AreEqual("a+b+c", extender.CanonicalRepresentation("b-a-c"));
+      Assert.AreEqual("a+b+E", extender.CanonicalRepresentation("b-a-E"));
+    }
+    [TestMethod]
+    public void TestFactorExpansion() {
+      var extender = new ExpressionExtender();
+      Assert.AreEqual("a+b", extender.CanonicalRepresentation("(b+a)"));
+      Assert.AreEqual("a+b", extender.CanonicalRepresentation("(b)+(a)"));
+      Assert.AreEqual("a+b", extender.CanonicalRepresentation("(b+(a))"));
+      Assert.AreEqual("a+b", extender.CanonicalRepresentation("((b)+a)"));
+
+      Assert.AreEqual("a+b+c", extender.CanonicalRepresentation("b-(a-c)"));
+      Assert.AreEqual("a+b+c", extender.CanonicalRepresentation("b-(a+c)"));
+      Assert.AreEqual("a+b+E", extender.CanonicalRepresentation("b-(a-E)"));
+
+      // when using constant opt the negative sign is not necessary because a negative factor can be produced
+      Assert.AreEqual("a*b+c*b", extender.CanonicalRepresentation("b*(c-a)"));
+      Assert.AreEqual("a*b+a*d+b*c+c*d", extender.CanonicalRepresentation("(b-d)*(c-a)"));
+    }
+    [TestMethod]
+    public void TestDivisionExpansion() {
+      var extender = new ExpressionExtender();
+      Assert.AreEqual("a%c+b%c", extender.CanonicalRepresentation("(b+a)%c"));
+      Assert.AreEqual("a%c%d+b%c%d", extender.CanonicalRepresentation("(b+a)%(d*c)"));
+      Assert.AreEqual("a%(c+d)+b%(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)"));
+      Assert.AreEqual("a*b%(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)"));
+
+      Assert.AreEqual("a*b%(a+b)%(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
+      Assert.AreEqual("a*b%(c+d)%(a%e+b%e)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
+      // a*b*e%(c+d)%(a+b)
+    }
+    [TestMethod]
+    public void TestDivisionCancellation() {
+      var extender = new ExpressionExtender();
+      Assert.AreEqual("a", extender.CanonicalRepresentation("a%a"));
+      Assert.AreEqual("a*a", extender.CanonicalRepresentation("a*a%a"));
+      Assert.AreEqual("1%a", extender.CanonicalRepresentation("(a%a)%a"));
+      Assert.AreEqual("1%a", extender.CanonicalRepresentation("a%a%a"));
+      Assert.AreEqual("a", extender.CanonicalRepresentation("a%(a%a)"));
+    }
+  }
+}
