source: branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Generators/CodeGenerator/RecursiveCodeGenerator.cs @ 14834

namespace HeuristicLab.Problems.ProgramSynthesis.Push.Generators.CodeGenerator {
  using System;
  using System.Collections.Generic;
  using System.Linq;
  using Configuration;
  using Core;
  using Data.Pool;
  using Expressions;

  using HeuristicLab.Random;

  /// <summary>
  ///     The following is the standard Push random code generation algorithm, which is used for the CODE.RAND instruction.
  ///     It may also be useful for the initialization of programs in evolutionary computation systems, and it is used for
  ///     this purpose in PushGP.
  ///     It produces a uniform distribution of sizes and what seems to be a reasonable distribution of shapes, in a
  ///     reasonable amount of time.
  /// </summary>
  /// <see cref="http://faculty.hampshire.edu/lspector/push3-description.html#RandomCode" />
  public class RecursiveCodeGenerator {

    public static PushProgram RandomProgram(IManagedPool<PushProgram> pool, int maxPoints, IRandom random = null, IReadOnlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
      var code = RandomCode(maxPoints, random, pushGpConfiguration, customExpressions);

      return PushProgram.Create(pool, code.ToArray());
    }

    public static PushProgram RandomProgram(int maxPoints, IRandom random = null, IReadOnlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
      var code = RandomCode(maxPoints, random, pushGpConfiguration, customExpressions);

      return new PushProgram(code.ToArray());
    }

    public static IEnumerable<Expression> RandomCode(int maxPoints, IRandom random = null, IReadOnlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
      if (maxPoints == 0)
        return new Expression[0];

      random = random ?? new FastRandom();
      pushGpConfiguration = pushGpConfiguration ?? new PushConfiguration();

      if (pushGpConfiguration.EnabledExpressions.Count == 0)
        return new Expression[0];

      var actualPoints = maxPoints == 1 ? 1 : random.Next(1, Math.Max(1, maxPoints));

      return RandomCodeWithSize(actualPoints, random, pushGpConfiguration, customExpressions);
    }

    private static IEnumerable<Expression> RandomCodeWithSize(int points, IRandom random, IReadOnlyPushConfiguration pushConfiguration, IDictionary<string, Expression> customExpressions = null) {
      if (points == 1) {
        return new[] { CodeGeneratorUtils.CreateExpressionOrErc(
          random,
          pushConfiguration.EnabledExpressions,
          pushConfiguration.ErcOptions,
          customExpressions)
        };
      }

      var maxParts = points - 1;

      return Decompose(maxParts, maxParts, random)
        .SelectMany(size => RandomCodeWithSize(size, random, pushConfiguration, customExpressions));
    }

    private static IEnumerable<int> Decompose(int number, int maxParts, IRandom random) {
      if ((number == 1) || (maxParts == 1))
        return new[] { number };

      var thisPart = number == 2 ? 1 : random.Next(1, number - 1);

      return new[] { thisPart }.Concat(Decompose(number - thisPart, maxParts - 1, random));
    }
  }
}