Index: /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/HashExtensions.cs
===================================================================
--- /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/HashExtensions.cs	(revision 16193)
+++ /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/HashExtensions.cs	(revision 16193)
@@ -0,0 +1,305 @@
+﻿using System;
+using System.Linq;
+using System.Security.Cryptography;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
+  public static class HashExtensions {
+    public sealed class Node : IComparable<Node>, IEquatable<Node> {
+      public Symbol Symbol;
+      public int Arity;
+      public bool Enabled;
+      public int Hash;
+      public int Size;
+
+      public bool IsChild => Arity == 0;
+
+      private Node(Symbol s, int n, bool e) {
+        Symbol = s;
+        Arity = Size = n;
+        Enabled = e;
+        Hash = Symbol.GetHashCode();
+      }
+
+      public static Node Make(Symbol s, int n, bool e = true) { return new Node(s, n, e); }
+
+      public int CompareTo(Node other) {
+        var res = Symbol.CompareTo(other.Symbol);
+        return res == 0 ? Hash.CompareTo(other.Hash) : res;
+      }
+
+      public override string ToString() {
+        return $"{Symbol} {Arity} {Size} {Hash} {Enabled}";
+      }
+
+      public bool Equals(Node other) {
+        return Symbol.Equals(other.Symbol) && Hash.Equals(other.Hash);
+      }
+
+      public override bool Equals(object obj) {
+        var other = obj as Node;
+        if (other != null)
+          return Equals(other);
+        return base.Equals(obj);
+      }
+
+      public override int GetHashCode() {
+        return Hash;
+      }
+
+      public static bool operator ==(Node a, Node b) {
+        return a.Equals(b);
+      }
+
+      public static bool operator !=(Node a, Node b) {
+        return !(a == b);
+      }
+    }
+
+    private static int Arity(this Grammar g, Symbol s) {
+      if (s == g.Addition || s == g.Multiplication)
+        return 2;
+
+      if (s == g.Log || s == g.Exp || s == g.Sin || s == g.Inv)
+        return 1;
+
+      return 0;
+    }
+
+    public static int ComputeHash(this Grammar grammar, HashAlgorithm ha, SymbolList sentence) {
+      var nodes = sentence.Select(x => Node.Make(x, grammar.Arity(x))).ToArray();
+      var simplified = grammar.Simplify(ha, nodes);
+
+      int hash = 1315423911;
+      foreach (var node in simplified)
+        hash ^= (hash << 5) + node.Hash + (hash >> 2);
+      return hash;
+
+      //var hashes = simplified.Select(x => x.Hash).ToArray();
+      //return BitConverter.ToInt32(ComputeHash(ha, hashes), 0);
+    }
+
+    public static SymbolList Simplify(this Grammar grammar, HashAlgorithm ha, SymbolList sentence) {
+      var nodes = sentence.Select(x => Node.Make(x, grammar.Arity(x))).ToArray();
+      return new SymbolList(grammar.Simplify(ha, nodes).Select(x => x.Symbol));
+    }
+
+    private static Node[] Simplify(this Grammar grammar, HashAlgorithm ha, Node[] nodes) {
+      var reduced = grammar.Reduce(nodes);
+      SortChildren(ha, reduced);
+
+      for (int i = 0; i < reduced.Length; ++i) {
+        var node = reduced[i];
+        if (node.IsChild) {
+          continue;
+        }
+
+        if (node.Symbol == grammar.Addition) {
+          grammar.SimplifyAddition(reduced, i);
+        } else if (node.Symbol == grammar.Multiplication) {
+          grammar.SimplifyMultiplication(reduced, i);
+        }
+      }
+      // detect if anything was simplified
+      var count = 0;
+      foreach (var node in reduced) {
+        if (!node.Enabled) { ++count; }
+      }
+      if (count == 0) {
+        return reduced;
+      }
+
+      var simplified = new Node[reduced.Length - count];
+      int j = 0;
+      foreach (var node in reduced) {
+        if (node.Enabled) {
+          simplified[j++] = node;
+        }
+      }
+      UpdateNodeSizes(simplified);
+      SortChildren(ha, simplified);
+      return simplified;
+    }
+
+    /// <summary>
+    /// This method will set @Node @Enabled flags to false for nodes that should be simplified
+    /// </summary>
+    /// <param name="nodes">The array of nodes representing the expression</param>
+    /// <param name="i">Index of the current node</param>
+    private static void SimplifyAddition(this Grammar grammar, Node[] nodes, int i) {
+      // simplify additions of terms by eliminating terms with the same symbol and hash
+      var children = IterateChildren(nodes, i);
+
+      var curr = children[0];
+      var node = nodes[i];
+
+      for (int j = 1; j < children.Length; ++j) {
+        var idx = children[j];
+        if (nodes[idx] == nodes[curr]) {
+          for (int k = idx - nodes[idx].Size; k <= idx; ++k) {
+            nodes[k].Enabled = false;
+          }
+          node.Arity--;
+        } else {
+          curr = idx;
+        }
+      }
+      if (node.Arity == 1) { // if the arity is 1 we don't need the addition node at all
+        node.Enabled = false;
+      }
+    }
+
+    private static void SimplifyMultiplication(this Grammar grammar, Node[] nodes, int i) {
+      // simplify multiplifactions by reducing inv terms for example a * 1/a -> c
+      var node = nodes[i];
+      var children = IterateChildren(nodes, i);
+      foreach (var c in children) {
+        if (nodes[c].Symbol == grammar.Inv) {
+          var denominator = nodes[c - 1];
+          foreach (var d in children) {
+            if (nodes[d].Enabled && nodes[d] == denominator) {
+              // the inv node can be simplified because the denominator matches another child
+              // disable the inv node, its child, and the matching child
+              nodes[d].Enabled = false;
+              nodes[c].Enabled = false;
+              nodes[c - 1].Enabled = false;
+              node.Arity -= 2;
+              break;
+            }
+          }
+
+          if (node.Arity == 0) { // if everything is simplified this node becomes constant
+            nodes[i] = Node.Make(grammar.Const, 0);
+          } else if (node.Arity == 1) { // when i have only 1 arg left i can skip this node
+            node.Enabled = false;
+          }
+        }
+      }
+    }
+
+    private static int ComputeHash(HashAlgorithm ha, Node[] nodes, int i) {
+      var node = nodes[i];
+      var hashes = new int[node.Arity + 1];
+      int idx = 0;
+      foreach (int c in IterateChildren(nodes, i)) {
+        hashes[idx++] = nodes[c].Hash;
+      }
+      hashes[idx] = node.Symbol.GetHashCode();
+      //return BitConverter.ToInt32(ComputeHash(ha, hashes), 0);
+      return HashUtil.JSHash(hashes);
+    }
+
+    private static void SortChildren(HashAlgorithm ha, Node[] nodes) {
+      for (int i = 0; i < nodes.Length; ++i) {
+        var node = nodes[i];
+
+        if (node.IsChild) {
+          continue;
+        }
+
+        var arity = node.Arity;
+        var size = node.Size;
+
+        if (arity == size) { // all child nodes are terminals
+          Array.Sort(nodes, i - size, size);
+        } else { // i have some non-terminal children
+          var sorted = new Node[size];
+          var indices = IterateChildren(nodes, i);
+          Array.Sort(indices, (a, b) => nodes[a].CompareTo(nodes[b]));
+
+          int idx = 0;
+          foreach (var j in indices) {
+            var child = nodes[j];
+            if (!child.IsChild) { // must copy complete subtree
+              Array.Copy(nodes, j - child.Size, sorted, idx, child.Size);
+              idx += child.Size;
+            }
+            sorted[idx++] = nodes[j];
+          }
+          Array.Copy(sorted, 0, nodes, i - size, size);
+        }
+        node.Hash = ComputeHash(ha, nodes, i);
+      }
+    }
+
+    /// <summary>
+    /// Get a function node's child indices from left to right
+    /// </summary>
+    /// <param name="nodes"></param>
+    /// <param name="i"></param>
+    /// <returns>An array containing child indices</returns>
+    private static int[] IterateChildren(Node[] nodes, int i) {
+      var node = nodes[i];
+      var arity = node.Arity;
+      var children = new int[arity];
+      var idx = i - 1;
+      for (int j = 0; j < arity; ++j) {
+        children[j] = idx;
+        idx -= 1 + nodes[idx].Size;
+      }
+      return children;
+    }
+
+    private static void UpdateNodeSizes(Node[] nodes) {
+      for (int i = 0; i < nodes.Length; ++i) {
+        var node = nodes[i];
+        if (node.IsChild) {
+          node.Size = 0;
+          continue;
+        }
+        node.Size = node.Arity;
+        foreach (var j in IterateChildren(nodes, i)) {
+          node.Size += nodes[j].Size;
+        }
+      }
+    }
+
+    /// <summary>
+    /// Reduce nodes of the same type according to arithmetic rules
+    /// </summary>
+    /// <param name="g">The given grammar (controls symbol arities)</param>
+    /// <param name="nodes">The node array</param>
+    /// <param name="i">Parent index</param>
+    /// <param name="j">Child index</param>
+    private static void Reduce(this Grammar g, Node[] nodes, int i, int j) {
+      var p = nodes[i]; // parent node
+      var c = nodes[j]; // child node
+
+      if (c.IsChild)
+        return;
+
+      foreach (var k in IterateChildren(nodes, j)) {
+        if (nodes[k].IsChild) continue;
+        g.Reduce(nodes, j, k);
+      }
+
+      // handle commutative symbols (add, mul) 
+      if (g.Arity(p.Symbol) == 2 && p.Symbol == c.Symbol) {
+        c.Enabled = false;
+        p.Arity += c.Arity - 1;
+      }
+    }
+
+    private static Node[] Reduce(this Grammar grammar, Node[] nodes) {
+      UpdateNodeSizes(nodes);
+      int i = nodes.Length - 1;
+      foreach (var c in IterateChildren(nodes, i)) {
+        if (nodes[c].IsChild) continue;
+        grammar.Reduce(nodes, i, c);
+      }
+      int count = 0;
+      foreach (var node in nodes) {
+        if (!node.Enabled) { ++count; }
+      }
+      if (count == 0)
+        return nodes;
+
+      var reduced = new Node[nodes.Length - count];
+      i = 0;
+      foreach (var node in nodes) {
+        if (node.Enabled) { reduced[i++] = node; }
+      }
+      UpdateNodeSizes(reduced);
+      return reduced;
+    }
+  }
+}
Index: /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/HashUtil.cs
===================================================================
--- /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/HashUtil.cs	(revision 16193)
+++ /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/HashUtil.cs	(revision 16193)
@@ -0,0 +1,79 @@
+﻿using System;
+using System.Security.Cryptography;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
+  public static class HashUtil {
+    // This class contains some hash functions adapted from http://partow.net/programming/hashfunctions/index.html#AvailableHashFunctions
+
+    // A simple hash function from Robert Sedgwicks Algorithms in C book.I've added some simple optimizations to the algorithm in order to speed up its hashing process. 
+    public static int RSHash(int[] input) {
+      const int b = 378551;
+      int a = 63689;
+      int hash = 0;
+
+      foreach (var v in input) {
+        hash = (hash * a) + v;
+        a *= b;
+      }
+      return hash;
+    }
+
+    // A bitwise hash function written by Justin Sobel
+    public static int JSHash(int[] input) {
+      int hash = 1315423911;
+      for (int i = 0; i < input.Length; ++i)
+        hash ^= (hash << 5) + input[i] + (hash >> 2);
+      return hash;
+    }
+
+    // This hash function comes from Brian Kernighan and Dennis Ritchie's book "The C Programming Language". It is a simple hash function using a strange set of possible seeds which all constitute a pattern of 31....31...31 etc, it seems to be very similar to the DJB hash function. 
+    public static int BKDRHash(int[] input) {
+      const int seed = 131;
+      int hash = 0;
+      foreach (var v in input) {
+        hash = (hash * seed) + v;
+      }
+      return hash;
+    }
+
+    // This is the algorithm of choice which is used in the open source SDBM project. The hash function seems to have a good over-all distribution for many different data sets. It seems to work well in situations where there is a high variance in the MSBs of the elements in a data set. 
+    public static int SDBMHash(int[] input) {
+      int hash = 0;
+      foreach (var v in input) {
+        hash = v + (hash << 6) + (hash << 16) - hash;
+      }
+      return hash;
+    }
+
+    // An algorithm produced by Professor Daniel J. Bernstein and shown first to the world on the usenet newsgroup comp.lang.c. It is one of the most efficient hash functions ever published. 
+    public static int DJBHash(int[] input) {
+      int hash = 5381;
+      foreach (var v in input) {
+        hash = (hash << 5) + hash + v;
+      }
+      return hash;
+    }
+
+    // An algorithm proposed by Donald E.Knuth in The Art Of Computer Programming Volume 3, under the topic of sorting and search chapter 6.4. 
+    public static int DEKHash(int[] input) {
+      int hash = input.Length;
+      foreach (var v in input) {
+        hash = (hash << 5) ^ (hash >> 27) ^ v;
+      }
+      return hash;
+    }
+
+    public static int CryptoHash(HashAlgorithm ha, int[] input) {
+      return BitConverter.ToInt32(ha.ComputeHash(input.ToByteArray()), 0);
+    }
+
+    public static byte[] ToByteArray(this int[] input) {
+      const int size = sizeof(int);
+      var bytes = new byte[input.Length * sizeof(int)];
+      for (int i = 0; i < input.Length; ++i) {
+        Array.Copy(BitConverter.GetBytes(bytes[i]), 0, bytes, i * size, size);
+      }
+      return bytes;
+    }
+  }
+}
Index: /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj
===================================================================
--- /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj	(revision 16192)
+++ /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj	(revision 16193)
@@ -128,4 +128,6 @@
     <Compile Include="Hashing\Hasher.cs" />
     <Compile Include="GrammarEnumeration\SearchDataStructure.cs" />
+    <Compile Include="Hashing\HashExtensions.cs" />
+    <Compile Include="Hashing\HashUtil.cs" />
     <Compile Include="ProblemInstances\AircraftMaximumLift.cs" />
     <Compile Include="ProblemInstances\FluidDynamics.cs" />
Index: /branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs
===================================================================
--- /branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs	(revision 16192)
+++ /branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs	(revision 16193)
@@ -1,7 +1,10 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
+using System.Security.Cryptography;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
+using HierarchicalFormatter = HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeHierarchicalFormatter;
 
 namespace Test {
@@ -15,4 +18,6 @@
     private TerminalSymbol c;
 
+    Func<Grammar, SymbolList, int> ComputeHash = (grammar, sentence) => grammar.ComputeHash(null, sentence);
+
     [TestInitialize]
     public void InitTest() {
@@ -31,6 +36,6 @@
       SymbolList s2 = new SymbolList(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -43,6 +48,6 @@
       SymbolList s2 = new SymbolList(new[] { varB, varB, grammar.Addition, varB, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreNotEqual(hash1, hash2);
@@ -55,6 +60,6 @@
       SymbolList s2 = new SymbolList(new[] { varB, varA, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -67,6 +72,6 @@
       SymbolList s2 = new SymbolList(new[] { varA, varB, varA, grammar.Addition, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -79,6 +84,6 @@
       SymbolList s2 = new SymbolList(new[] { varA });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -91,6 +96,6 @@
       SymbolList s2 = new SymbolList(new[] { varA, varA, varA, grammar.Multiplication, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreNotEqual(hash1, hash2);
@@ -103,6 +108,6 @@
       SymbolList s2 = new SymbolList(new Symbol[] { varA, grammar.Expr, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -117,6 +122,6 @@
       SymbolList s2 = new SymbolList(new Symbol[] { varA, varB, grammar.Multiplication });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -129,6 +134,17 @@
       SymbolList s2 = new SymbolList(new Symbol[] { varA, varA, varA, grammar.Multiplication, grammar.Addition, grammar.Sin, varA, grammar.Inv, varA, grammar.Sin, varA, grammar.Multiplication, grammar.Multiplication, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
+
+      Console.WriteLine(s1);
+      Console.WriteLine(PrintTree(s1));
+      Console.WriteLine(grammar.Simplify(null, s1));
+      Console.WriteLine(hash1);
+      Console.WriteLine();
+      Console.WriteLine(s2);
+      Console.WriteLine(PrintTree(s2));
+      Console.WriteLine(grammar.Simplify(null, s2));
+      Console.WriteLine(hash2);
+
 
       Assert.AreEqual(hash1, hash2);
@@ -142,6 +158,6 @@
       SymbolList s2 = new SymbolList(new Symbol[] { c, varA, grammar.Multiplication, c, varA, grammar.Multiplication, grammar.Addition, c, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -153,22 +169,152 @@
       //const int nvars = 1;
       //var variables = Enumerable.Range(1, nvars).Select(x => $"x{x}").ToArray();
+      var variables = new[] { "a", "b" };
+      var grammar = new Grammar(variables, Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>());
+
+      Func<SymbolList, int> hash = s => grammar.Hasher.CalcHashCode(s);
+      int length = 100;
+      int depth = 20;
+
+      //List<SymbolList> sentences = EnumerateGrammarBreadth(grammar, length: length, hashPhrases: false).ToList();
+      //Console.WriteLine("Breadth: {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
+
+      //var sentences = EnumerateGrammarBreadth(grammar, length: length, hashPhrases: true).ToList();
+      //Console.WriteLine("Breadth (hashed): {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
+
+      var sentences = EnumerateGrammarDepth(grammar, length: length, depth: depth, hashPhrases: false).ToList();
+      Console.WriteLine("Depth: {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
+
+      sentences = EnumerateGrammarDepth(grammar, length: length, depth: depth, hashPhrases: true).ToList();
+      Console.WriteLine("Depth (hashed): {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
+    }
+
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void HashExtensionsTest() {
+      var variables = new[] { "x", "y", "z" };
+      var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>();
+      var grammar = new Grammar(variables, rules);
+      var add = grammar.Addition;
+      var mul = grammar.Multiplication;
+      var exp = grammar.Exp;
+      var log = grammar.Log;
+      var inv = grammar.Inv;
+      var sin = grammar.Sin;
+
+      var c = grammar.Const;
+      var x = grammar.VarTerminals.Single(v => v.StringRepresentation == "x");
+      var y = grammar.VarTerminals.Single(v => v.StringRepresentation == "y");
+      var z = grammar.VarTerminals.Single(v => v.StringRepresentation == "z");
+
+
+      var ha = SHA512.Create();
+
+      var sentences = new[] {
+        new SymbolList(c, c, x, mul, c, add, inv, mul, c, add),
+        new SymbolList(c, c, x, mul, c, add, log, mul, c, add),
+        new SymbolList(x, x, add),
+        new SymbolList(x, x, add, x, add),
+        new SymbolList(x, x, add, y, add),
+        new SymbolList(x, x, add, x, add, x, add),
+        new SymbolList(x, x, add, y, add, x, add),
+        new SymbolList(x, y, mul, x, y, mul, add),
+        new SymbolList(x, y, mul, y, x, mul, add),
+        new SymbolList(x, y, mul, z, y, mul, add),
+        new SymbolList(x, x, add, y, mul),
+        new SymbolList(x, x, add, y, mul, y, mul),
+        new SymbolList(x, x, inv, mul),
+        new SymbolList(x, inv, x, inv, mul, x, mul, x, mul),
+        new SymbolList(c, x, x, x, x, x, x, mul, mul, mul, mul, mul, mul, c, x, mul, c, add, add),
+        new SymbolList(c, x, x, x, x, x, x, mul, mul, mul, mul, mul, mul, c, x, mul, c, add, add),
+        new SymbolList(c, x, mul, c, x, x, x, x, x, x, mul, mul, mul, mul, mul, mul, c, add, add),
+        new SymbolList(c, x, x, x, x, mul, mul, mul, mul, c, x, mul, c, x, mul, c, add, add, add),
+        new SymbolList(c, x, mul, c, x, x, x, x, mul, mul, mul, mul, c, x, mul, c, add, add, add)
+    };
+
+      foreach (var sentence in sentences) {
+        var simplified = grammar.Simplify(ha, sentence);
+        Console.WriteLine($"{sentence} -> {simplified} {grammar.Hasher.CalcHashCode(sentence)} {grammar.ComputeHash(ha, sentence)}");
+        Console.WriteLine();
+      }
+    }
+
+    string PrintTree(SymbolList s) {
+      var t = grammar.ParseSymbolicExpressionTree(s);
+      return HierarchicalFormatter.Format(t.Root.GetSubtree(0).GetSubtree(0));
+    }
+
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void HashCollisionsTest() {
       var variables = new[] { "x", "y", "z", "w" };
-      var grammar = new Grammar(variables, Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>());
-
-      Func<SymbolList, int> hash = s => grammar.Hasher.CalcHashCode(s);
-
-      List<SymbolList> sentences = EnumerateGrammarBreadth(grammar, length: 20, hashPhrases: false).ToList();
-      Console.WriteLine("Breadth: {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
-
-      sentences = EnumerateGrammarBreadth(grammar, length: 20, hashPhrases: true).ToList();
-      Console.WriteLine("Breadth (hashed): {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
-
-      sentences = EnumerateGrammarDepth(grammar, length: 20, hashPhrases: false).ToList();
-      Console.WriteLine("Depth: {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
-
-      sentences = EnumerateGrammarDepth(grammar, length: 20, hashPhrases: true).ToList();
-      Console.WriteLine("Depth (hashed): {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
-    }
-
+      //var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>().Except(new[] { GrammarRule.InverseTerm, GrammarRule.Exponentiation, GrammarRule.Logarithm, GrammarRule.Sine });
+      var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>();
+      var grammar = new Grammar(variables, rules);
+
+      int maxLength = 20, maxDepth = int.MaxValue;
+      var sentences = EnumerateGrammarDepth(grammar, length: maxLength, depth: maxDepth, hashPhrases: false).ToList();
+      var count = sentences.Count;
+
+      var sw = new Stopwatch();
+      sw.Start();
+      var hashes = sentences.Select(grammar.Hasher.CalcHashCode).ToList();
+      sw.Stop();
+      Console.WriteLine($"Old hash: {sentences.Count} ({hashes.Distinct().Count()}) hashed in {sw.ElapsedMilliseconds / 1000.0} seconds ({1000d * sentences.Count / sw.ElapsedMilliseconds} hashes/s)");
+
+      var ha = SHA512.Create();
+      sw.Restart();
+      var hashes_new = sentences.Select(x => grammar.ComputeHash(ha, x)).ToList();
+      sw.Stop();
+      Console.WriteLine($"New hash: {sentences.Count} ({hashes_new.Distinct().Count()}) hashed in {sw.ElapsedMilliseconds / 1000.0} seconds ({1000.0 * sentences.Count / sw.ElapsedMilliseconds} hashes/s)");
+
+      var distinct = Enumerable.Range(0, count).GroupBy(x => hashes_new[x]).Select(g => g.OrderBy(x => x).First()).ToList();
+      var collisions = distinct.ToLookup(x => hashes[x], x => Tuple.Create(hashes_new[x], sentences[x]));
+
+      foreach (var pair in collisions) {
+        if (pair.Count() > 1) {
+          Console.WriteLine(pair.Key);
+          foreach (var t in pair) {
+            Console.WriteLine($"\t{t}");
+            Console.WriteLine($"\t{grammar.ToInfixString(t.Item2)}");
+            var simplified = grammar.Simplify(ha, t.Item2);
+            Console.WriteLine($"\t{simplified}");
+            Console.Write($"\t");
+            PrintTree(t.Item2);
+            Console.WriteLine();
+          }
+        }
+      }
+    }
+
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void HashPerformance() {
+      var nvars = 4;
+      var variables = Enumerable.Range(0, nvars).Select(x => $"X{x}").ToArray();
+      //var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>().Except(new[] { GrammarRule.InverseTerm, GrammarRule.Exponentiation, GrammarRule.Logarithm, GrammarRule.Sine });
+      var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>();
+      var grammar = new Grammar(variables, rules);
+
+      int maxLength = 20, maxDepth = int.MaxValue;
+      var sentences = EnumerateGrammarDepth(grammar, length: maxLength, depth: maxDepth, hashPhrases: false).ToList();
+      var count = sentences.Count;
+
+      var ha = SHA512.Create();
+
+      var sw = new Stopwatch();
+      sw.Start();
+      var hashes = sentences.Select(x => grammar.ComputeHash(ha, x)).ToList();
+      sw.Stop();
+
+      Console.WriteLine($"New: {sentences.Count} ({hashes.Distinct().Count()}) hashed in {sw.ElapsedMilliseconds / 1000.0} seconds ({1000d * sentences.Count / sw.ElapsedMilliseconds} hashes/s)");
+
+      sw.Restart();
+      var hashes_old = sentences.Select(x => grammar.Hasher.CalcHashCode(x)).ToList();
+      sw.Stop();
+
+      Console.WriteLine($"Old: {sentences.Count} ({hashes_old.Distinct().Count()}) hashed in {sw.ElapsedMilliseconds / 1000.0} seconds ({1000d * sentences.Count / sw.ElapsedMilliseconds} hashes/s)");
+    }
+
+    #region enumerate the grammar
     private static IEnumerable<SymbolList> EnumerateGrammarBreadth(Grammar grammar, int length, bool hashPhrases = true) {
       var phrases = new Queue<SymbolList>();
@@ -201,10 +347,10 @@
     }
 
-    private static IEnumerable<SymbolList> EnumerateGrammarDepth(Grammar grammar, int length, bool hashPhrases = true) {
-      return Expand(new SymbolList(grammar.StartSymbol), grammar, length, hashPhrases ? new HashSet<int>() : null);
-    }
-
-    private static IEnumerable<SymbolList> Expand(SymbolList phrase, Grammar grammar, int maxLength, HashSet<int> visited) {
-      if (phrase.Count > maxLength) {
+    private static IEnumerable<SymbolList> EnumerateGrammarDepth(Grammar grammar, int length, int depth, bool hashPhrases = true) {
+      return Expand(new SymbolList(grammar.StartSymbol), grammar, length, 0, depth, hashPhrases ? new HashSet<int>() : null);
+    }
+
+    private static IEnumerable<SymbolList> Expand(SymbolList phrase, Grammar grammar, int maxLength, int depth, int maxDepth, HashSet<int> visited) {
+      if (maxDepth < depth || maxLength < phrase.Count) {
         yield break;
       }
@@ -215,5 +361,5 @@
       }
 
-      if (visited != null && !visited.Add(grammar.Hasher.CalcHashCode(phrase))) {
+      if (visited != null && !visited.Add(HashExtensions.ComputeHash(grammar, null, phrase))) {
         yield break;
       }
@@ -222,7 +368,8 @@
       var productions = grammar.Productions[phrase[i]];
 
-      foreach (var s in productions.SelectMany(p => Expand(phrase.DerivePhrase(i, p), grammar, maxLength, visited)))
+      foreach (var s in productions.SelectMany(p => Expand(phrase.DerivePhrase(i, p), grammar, maxLength, depth + 1, maxDepth, visited)))
         yield return s;
     }
+    #endregion
   }
 }
