Algorithm to find optimal day/month/year intervals to in an arbitrary timeframe?

If you have a timeframe, say:

March 19, 2009 - July 15, 2011

Is there an algorithm that will break that timeframe down into this:

March 19, 2009  - March 31, 2009    # complete days
April 1, 2009   - December 31, 2009 # complete months
January 1, 2010 - December 31, 2010 # complete years
January 1, 2011 - June 30, 2011     # complete months
July 1, 2011    - July 15, 2011     # complete days

More specifically, given any arbitrary timeframe, even down to the second, is there an algorithm that can divide that up into the optimal number of arbitrarily sized intervals?

So, maybe instead of dividing the above date range into days/months/years you wanted to divide it up into 5 day and 18 month chunks, something random like that. Is there a formal name for this type of algorithm? A ruby example would be awesome, but any language works.开发者_Python百科

I've been able to hack together some hardcoded Ruby thing to handle the day/month/year example:

• https://gist.github.com/1165914

...but it seems like there should be an algorithm to abstract this to handle any interval breakdown. Maybe it just boils down to simple math.

This may be cheating but you can simplify the code greatly by using the date functions provided by active_support. Below is some code that I came up with using active_support. The algorithm is pretty simple. Figure out the last day of the first month, figure out the first day of the last month. Then print the first month, split the middle into years and print them, then print the last month. Of course, this simple algorithm falls down in a number of ways due to edge cases. The following algorithm attempts to address each of these edge cases gracefully. I hope that it helps.

require 'active_support/all'

# Set the start date and end date
start_date = Date.parse("March 19, 2009")
end_date = Date.parse("July 15, 2011")

if end_date < start_date
  # end date is before start date, we are done
elsif end_date == start_date
  # end date is the same as start date, print it and we are done
  print start_date.strftime("%B %e, %Y")
elsif start_date.year == end_date.year && start_date.month == end_date.month
  # start date and end date are in the same month, print the dates and we
  # are done
  print start_date.strftime("%B %e, %Y"), " - ",
    end_date.strftime("%B %e, %Y"), "\n"
else
  # start date and end date are in different months
  first_day_of_next_month = Date.new((start_date + 1.month).year,
    (start_date + 1.month).month, 1);
  first_day_of_end_month = Date.new(end_date.year, end_date.month, 1);

  # print out the dates of the first month
  if (first_day_of_next_month - 1.day) == start_date
    print start_date.strftime("%B %e, %Y"), "\n"
  else
    print start_date.strftime("%B %e, %Y"), " - ",
      (first_day_of_next_month - 1.day).strftime("%B %e, %Y"), "\n"
  end

  # now print the inbetween dates
  if first_day_of_next_month.year == (first_day_of_end_month - 1.day).year &&
    (first_day_of_end_month - 1.day) > first_day_of_next_month
    # start date and end date are in the same year, just print the inbetween
    # dates 
    print first_day_of_next_month.strftime("%B %e, %Y"), " - ",
      (first_day_of_end_month - 1.day).strftime("%B %e, %Y") + "\n"
  elsif first_day_of_next_month.year < (first_day_of_end_month - 1.day).year
    # start date and end date are in different years so we need to split across
    # years
    year_iter = first_day_of_next_month.year

    # print out the dates from the day after the first month to the end of the
    # year
    print first_day_of_next_month.strftime("%B %e, %Y"), " - ",
      Date.new(first_day_of_next_month.year, 12, 31).strftime("%B %e, %Y"),
      "\n"
    year_iter += 1

    # print out the full intermediate years
    while year_iter < end_date.year
      print Date.new(year_iter, 1, 1).strftime("%B %e, %Y"), " - ",
        Date.new(year_iter, 12, 31).strftime("%B %e, %Y"), "\n"
      year_iter += 1
    end

    # print from the begining of the last year until the last day before the the
    # end month
    print Date.new(first_day_of_end_month.year, 1, 1).strftime("%B %e, %Y"),
      " - ", (first_day_of_end_month - 1.day).strftime("%B %e, %Y"), "\n"
  end

  # finally print out the days of the last month
  if first_day_of_end_month == end_date
    print end_date.strftime("%B %e, %Y"), "\n"
  else
    print first_day_of_end_month.strftime("%B %e, %Y"), " - ",
      end_date.strftime("%B %e, %Y"), "\n"
  end
end

The original problem is in some sense very easy, because a year is made of months and a month is made of days. Hence you can just look at what chunks of your range are complete years, take these out, and iteratively look in what's left over for complete instances of the next-smaller unit.

In an arbitrary case, this need not be true. In your example, not every 18-month span is divisible into five-day intervals. This complicates things quite a bit because you can no longer rely on this hierarchy of units.

Another complication for arbitrary cases is that not every range has a feasible breakdown. In your example, Jan 1, 2011 - Jan 4, 2011 can not be decomposed into chunks of five days and 18 months.

I would hence suggest you try to formulate a more constrained version of the problem :)

This gets slightly more complicated once you bring the different sizes of months into the mix, but with a good date library the same concept should work (and probably make the "advancement" bit easier).

What started as psudocode ended as python - sorry about that.

intervals = [1, 60, 3600] # second minute hour
epoc = 0 # simple example case
start = 4 # 4 seconds past epoc
end = 7292 # 2:1:32

i = start
while i < end:
  for iidx, interval in enumerate(intervals):
    nIval = 0
    if(iidx+1 < len(intervals)):
      nIval = intervals[iidx+1]
    # wind down - find the next smallest interval that doesn't push us past END
    if (i-epoc) % interval == 0 and (i + nIval > end or not nIval):
      # move as close to end as possible
      pre = i
      while i+interval <= end:
        i += interval
      print "Stepped down %i to %i via %i" % (pre, i, interval)
    # wind up - find the next biggest interval boundary not past END
    elif nIval and (i-epoc) % nIval != 0:
      # advance to that interval boundry
      pre = i
      while (i-epoc) % nIval != 0 and i+interval <= end:
        i += interval
      print "Stepped up %i to %i via %i" % (pre, i, interval)
    if i == end:
      break