确定一组日期的事件重复模式

我正在寻找一种模式、算法或库，它将采用一组日期并在退出时返回重复的描述，即集合 [11-01-2010, 11-08-2010, 11-15-2010 , 11-22-2010, 11-29-2010] 会产生类似“十一月的每个星期一”的结果。

有没有人以前见过这样的事情或者对实施它的最佳方法有任何建议？

语法进化（GE） http://en.wikipedia.org/wiki/Grammatical_evolution适合此类问题，因为您正在寻找遵循某种语言的答案。语法进化还用于程序生成、作曲、设计等。

我会这样处理这个任务：

用语法构建问题空间.

构建一个上下文无关语法 http://en.wikipedia.org/wiki/Context-free_grammar可以代表所有所需的重复模式。考虑如下生产规则：

datepattern -> datepattern 'and' datepattern
datepattern -> frequency bounds
frequency -> 'every' ordinal weekday 'of the month'
frequency -> 'every' weekday
ordinal -> ordinal 'and' ordinal
ordinal -> 'first' | 'second' | 'third'
bounds -> 'in the year' year

由这些规则生成的模式的示例是：'2010 年每月的第二个和第三个星期三以及 2011 年的每个星期二'

实现这种语法的一种方法是通过类层次结构，稍后您将通过反射对其进行操作，就像我在下面的示例中所做的那样。

将此语言映射到一组日期

您应该创建一个函数，从您的语言中获取一个子句，并递归地返回它所涵盖的所有日期的集合。这使您可以将您的答案与输入进行比较。

以语法为指导，寻找潜在的解决方案

您可以使用遗传算法或模拟退火将日期与语法进行匹配，使用动态编程试试运气，或者从简单地暴力枚举所有可能的子句开始。

如果您使用遗传算法，您的变异概念应该包括根据您的生产规则之一的应用将一个表达式替换为另一个表达式。

请查看以下 GE 相关网站以获取代码和信息：http://www.bangor.ac.uk/~eep201/jge/ http://www.bangor.ac.uk/~eep201/jge/
http://nohejl.name/age/ http://nohejl.name/age/
http://www.genicprogramming.us/Home_Page.html http://www.geneticprogramming.us/Home_Page.html

评估每个解决方案

适应度函数可以考虑解决方案的文本长度、多次生成的日期的数量、错过的日期的数量以及生成的错误日期的数量。

示例代码

根据要求，并且因为这是一个非常有趣的挑战，我编写了该算法的基本实现来帮助您入门。虽然它可以工作，但还没有完成，但设计绝对应该得到更多的思考，一旦您从这个示例中收集到基本要点，我建议您考虑使用我上面提到的库之一。

  /// <summary>
  ///  This is a very basic example implementation of a grammatical evolution algorithm for formulating a recurrence pattern in a set of dates.
  ///  It needs significant extensions and optimizations to be useful in a production setting.
  /// </summary>
  static class Program
  {

    #region "Class hierarchy that codifies the grammar"

    class DatePattern
    {

      public Frequency frequency;
      public Bounds bounds;

      public override string ToString() { return "" + frequency + " " + bounds; }

      public IEnumerable<DateTime> Dates()
      {
        return frequency == null ? new DateTime[] { } : frequency.FilterDates(bounds.GetDates());
      }

    }

    abstract class Bounds
    {
      public abstract IEnumerable<DateTime> GetDates();
    }

    class YearBounds : Bounds
    {

      /* in the year .. */
      public int year;

      public override string ToString() { return "in the year " + year; }

      public override IEnumerable<DateTime> GetDates()
      {
        var firstDayOfYear = new DateTime(year, 1, 1);
        return Enumerable.Range(0, new DateTime(year, 12, 31).DayOfYear)
          .Select(dayOfYear => firstDayOfYear.AddDays(dayOfYear));
      }
    }

    abstract class Frequency
    {
      public abstract IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates);
    }

    class WeeklyFrequency : Frequency
    {

      /* every .. */
      public DayOfWeek dayOfWeek;

      public override string ToString() { return "every " + dayOfWeek; }

      public override IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates)
      {
        return Dates.Where(date => (date.DayOfWeek == dayOfWeek));
      }

    }

    class MonthlyFrequency : Frequency
    {

      /* every .. */
      public Ordinal ordinal;
      public DayOfWeek dayOfWeek;
      /* .. of the month */

      public override string ToString() { return "every " + ordinal + " " + dayOfWeek + " of the month"; }

      public override IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates)
      {
        return Dates.Where(date => (date.DayOfWeek == dayOfWeek) && (int)ordinal == (date.Day - 1) / 7);
      }

    }

    enum Ordinal { First, Second, Third, Fourth, Fifth }

    #endregion

    static Random random = new Random();
    const double MUTATION_RATE = 0.3;
    static Dictionary<Type, Type[]> subtypes = new Dictionary<Type, Type[]>();

    static void Main()
    {

      // The input signifies the recurrence 'every first thursday of the month in 2010':
      var input = new DateTime[] {new DateTime(2010,12,2), new DateTime(2010,11,4),new DateTime(2010,10,7),new DateTime(2010,9,2),
                    new DateTime(2010,8,5),new DateTime(2010,7,1),new DateTime(2010,6,3),new DateTime(2010,5,6),
                    new DateTime(2010,4,1),new DateTime(2010,3,4),new DateTime(2010,2,4),new DateTime(2010,1,7) };


      for (int cTests = 0; cTests < 20; cTests++)
      {
        // Initialize with a random population
        int treesize = 0;
        var population = new DatePattern[] { (DatePattern)Generate(typeof(DatePattern), ref treesize), (DatePattern)Generate(typeof(DatePattern), ref treesize), (DatePattern)Generate(typeof(DatePattern), ref treesize) };
        Run(input, new List<DatePattern>(population));
      }
    }

    private static void Run(DateTime[] input, List<DatePattern> population)
    {
      var strongest = population[0];
      int strongestFitness = int.MinValue;
      int bestTry = int.MaxValue;
      for (int cGenerations = 0; cGenerations < 300 && strongestFitness < -100; cGenerations++)
      {
        // Select the best individuals to survive:
        var survivers = population
            .Select(individual => new { Fitness = Fitness(input, individual), individual })
            .OrderByDescending(pair => pair.Fitness)
            .Take(5)
            .Select(pair => pair.individual)
            .ToArray();
        population.Clear();

        // The survivers are the foundation for the next generation:
        foreach (var parent in survivers)
        {
          for (int cChildren = 0; cChildren < 3; cChildren++)
          {
            int treeSize = 1;
            DatePattern child = (DatePattern)Mutate(parent, ref treeSize); // NB: procreation may also be done through crossover.
            population.Add((DatePattern)child);

            var childFitness = Fitness(input, child);
            if (childFitness > strongestFitness)
            {
              bestTry = cGenerations;
              strongestFitness = childFitness;
              strongest = child;
            }

          }
        }
      }
      Trace.WriteLine("Found best match with fitness " + Fitness(input, strongest) + " after " + bestTry + " generations: " + strongest);

    }

    private static object Mutate(object original, ref int treeSize)
    {
      treeSize = 0;


      object replacement = Construct(original.GetType());
      foreach (var field in original.GetType().GetFields())
      {
        object newFieldValue = field.GetValue(original);
        int subtreeSize;
        if (field.FieldType.IsEnum)
        {
          subtreeSize = 1;
          if (random.NextDouble() <= MUTATION_RATE)
            newFieldValue = ConstructRandomEnumValue(field.FieldType);
        }
        else if (field.FieldType == typeof(int))
        {
          subtreeSize = 1;
          if (random.NextDouble() <= MUTATION_RATE)
            newFieldValue = (random.Next(2) == 0
            ? Math.Min(int.MaxValue - 1, (int)newFieldValue) + 1
            : Math.Max(int.MinValue + 1, (int)newFieldValue) - 1);
        }
        else
        {
          subtreeSize = 0;
          newFieldValue = Mutate(field.GetValue(original), ref subtreeSize); // mutate pre-maturely to find out subtreeSize

          if (random.NextDouble() <= MUTATION_RATE / subtreeSize) // makes high-level nodes mutate less.
          {
            subtreeSize = 0; // init so we can track the size of the subtree soon to be made.
            newFieldValue = Generate(field.FieldType, ref subtreeSize);
          }
        }
        field.SetValue(replacement, newFieldValue);
        treeSize += subtreeSize;
      }
      return replacement;

    }

    private static object ConstructRandomEnumValue(Type type)
    {
      var vals = type.GetEnumValues();
      return vals.GetValue(random.Next(vals.Length));
    }

    private static object Construct(Type type)
    {
      return type.GetConstructor(new Type[] { }).Invoke(new object[] { });
    }

    private static object Generate(Type type, ref int treesize)
    {
      if (type.IsEnum)
      {
        return ConstructRandomEnumValue(type);
      }
      else if (typeof(int) == type)
      {
        return random.Next(10) + 2005;
      }
      else
      {
        if (type.IsAbstract)
        {
          // pick one of the concrete subtypes:
          var subtypes = GetConcreteSubtypes(type);
          type = subtypes[random.Next(subtypes.Length)];
        }
        object newobj = Construct(type);

        foreach (var field in type.GetFields())
        {
          treesize++;
          field.SetValue(newobj, Generate(field.FieldType, ref treesize));
        }
        return newobj;
      }
    }


    private static int Fitness(DateTime[] input, DatePattern individual)
    {
      var output = individual.Dates().ToArray();
      var avgDateDiff = Math.Abs((output.Average(d => d.Ticks / (24.0 * 60 * 60 * 10000000)) - input.Average(d => d.Ticks / (24.0 * 60 * 60 * 10000000))));
      return
        -individual.ToString().Length // succinct patterns are preferred.
        - input.Except(output).Count() * 300 // Forgetting some of the dates is bad.
        - output.Except(input).Count() * 3000 // Spurious dates cause even more confusion to the user.
      - (int)(avgDateDiff) * 30000; // The difference in average date is the most important guide.
    }

    private static Type[] GetConcreteSubtypes(Type supertype)
    {
      if (subtypes.ContainsKey(supertype))
      {
        return subtypes[supertype];
      }
      else
      {

        var types = AppDomain.CurrentDomain.GetAssemblies().ToList()
            .SelectMany(s => s.GetTypes())
            .Where(p => supertype.IsAssignableFrom(p) && !p.IsAbstract).ToArray();
        subtypes.Add(supertype, types);
        return types;
      }
    }
  }

希望这能让你走上正轨。请务必在某处分享您的实际解决方案；我认为它在很多场景下都会非常有用。