Index: branches/GP-MoveOperators/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Moves/ChangeNodeTypeMultiMoveGenerator.cs
===================================================================
--- branches/GP-MoveOperators/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Moves/ChangeNodeTypeMultiMoveGenerator.cs	(revision 7802)
+++ branches/GP-MoveOperators/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Moves/ChangeNodeTypeMultiMoveGenerator.cs	(revision 7832)
@@ -20,5 +20,4 @@
 #endregion
 
-using System;
 using System.Collections.Generic;
 using System.Linq;
@@ -46,6 +45,6 @@
       set { SampleSizeParameter.Value = value; }
     }
-    public ILookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter {
-      get { return (ILookupParameter<SymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
+    public ILookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
+      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
     }
     public ILookupParameter<ChangeNodeTypeMove> ChangeNodeTypeMoveParameter {
@@ -64,5 +63,5 @@
       Parameters.Add(new ValueLookupParameter<IntValue>("SampleSize", "The number of moves to generate."));
 
-      Parameters.Add(new LookupParameter<SymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree for which moves should be generated."));
+      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree for which moves should be generated."));
       Parameters.Add(new LookupParameter<ChangeNodeTypeMove>("ChangeNodeTypeMove", "The moves that should be generated in subscopes."));
       Parameters.Add(new ScopeParameter("CurrentScope", "The current scope where the moves should be added as subscopes."));
@@ -75,6 +74,7 @@
 
     public override IOperation Apply() {
-      SymbolicExpressionTree tree = SymbolicExpressionTreeParameter.ActualValue;
-      var moves = ChangeNodeTypeMoveGenerator.GenerateMoves(tree).ToArray();
+      var tree = SymbolicExpressionTreeParameter.ActualValue;
+
+
       string moveParameterName = ChangeNodeTypeMoveParameter.ActualName;
       var moveScopes = new List<Scope>();
@@ -82,9 +82,7 @@
       int n = SampleSizeParameter.ActualValue.Value;
 
-      var rand = Enumerable.Range(0, moves.Length).Select(i => random.NextDouble()).ToArray();
-      Array.Sort(rand, moves);
-      n = Math.Min(n, moves.Length);
+      var moves = GenerateMoves(tree, random, n);
 
-      foreach (var m in moves.Take(n)) {
+      foreach (var m in moves) {
         if (m.NewChild.HasLocalParameters)
           m.NewChild.ResetLocalParameters(random);
@@ -96,4 +94,27 @@
       return base.Apply();
     }
+
+    public static IEnumerable<ChangeNodeTypeMove> GenerateMoves(ISymbolicExpressionTree tree, IRandom random, int n) {
+      int count = 0;
+      var g = tree.Root.Grammar;
+      var possibleChildren = (from parent in tree.Root.GetSubtree(0).IterateNodesPrefix()
+                              from i in Enumerable.Range(0, parent.SubtreeCount)
+                              from s in g.GetAllowedChildSymbols(parent.Symbol, i)
+                              where s.Enabled
+                              where s.InitialFrequency > 0.0
+                              let currentChild = parent.GetSubtree(i)
+                              where s.MinimumArity >= currentChild.SubtreeCount
+                              where s.MaximumArity <= currentChild.SubtreeCount
+                              where (from j in Enumerable.Range(0, currentChild.SubtreeCount)
+                                     let childOfChild = currentChild.GetSubtree(j)
+                                     select g.IsAllowedChildSymbol(s, childOfChild.Symbol, j)).All(p => p)
+                              select new { parent, i, s }).ToArray();
+      if (possibleChildren.Length < n) n = possibleChildren.Length;
+      while (count < n) {
+        var selected = possibleChildren[random.Next(possibleChildren.Length)];
+        yield return new ChangeNodeTypeMove(tree, selected.parent, selected.i, selected.s.CreateTreeNode());
+        count++;
+      }
+    }
   }
 }
