Getting Random Durations within a range in C#

Question

For a random event generator I'm writing I need a simple algorithm to generate random ranges.

So, for example:

I may say I want 10 random intervals, between 1/1 and 1/7, with no overlap, in the states (1,2,3) where state 1 events add up to 1 day, state 2 events add up to 2 days and state 3 events add up to the rest.

Or in code:

struct Interval
{
    public DateTime Date;
    public long Duration; 
    public int State; 
}

struct StateSummary
{
    public int State;
    public long TotalSeconds; 
}

public Interval[] GetRandomIntervals(DateTime start, DateTime end, StateSummary[] sums, int totalEvents)
{
  // insert your cool algorithm here 
}

I'm working on this now, but in case someone beats me to a solution (or knows of an elegant pre-existing algorithm) I'm posting this on SO.

Answer 1

First use DateTime.Subtract to determine how many minutes/seconds/whatever between your min and max dates. Then use Math.Random to get a random number of minutes/seconds/whatever in that range. Then use the result of that to construct another TimeSpan instance and add that to your min DateTime.

Answer 2

Here's an implementation that compiles and works, although it's still somewhat rough. It requires that the input state array properly account for the entire time range of interest (end - start), but it would be trivial to add a bit of code that would make the final state fill up the time not accounted for in the first N-1 states. I also modified your structure definitions to use ints instead of longs for the durations, just to simplify things a bit.

For clarity (and laziness) I omitted all error checking. It works fine for the inputs like the ones you described, but it's by no means bulletproof.

public static Interval[] GetRandomIntervals( DateTime start, DateTime end,
    StateSummary[] states, int totalIntervals )
{
    Random r = new Random();

    // stores the number of intervals to generate for each state
    int[] intervalCounts = new int[states.Length];

    int intervalsTemp = totalIntervals;

    // assign at least one interval for each of the states
    for( int i = 0; i < states.Length; i++ )
        intervalCounts[i] = 1;
    intervalsTemp -= states.Length;

    // assign remaining intervals randomly to the various states
    while( intervalsTemp > 0 )
    {
        int iState = r.Next( states.Length );
        intervalCounts[iState] += 1;
        intervalsTemp -= 1;
    }

    // make a scratch copy of the state array
    StateSummary[] statesTemp = (StateSummary[])states.Clone();

    List<Interval> result = new List<Interval>();
    DateTime next = start;
    while( result.Count < totalIntervals )
    {
        // figure out which state this interval will go in (this could
        // be made more efficient, but it works just fine)
        int iState = r.Next( states.Length );
        if( intervalCounts[iState] < 1 )
            continue;
        intervalCounts[iState] -= 1;

        // determine how long the interval should be
        int length;
        if( intervalCounts[iState] == 0 )
        {
            // last one for this state, use up all remaining time
            length = statesTemp[iState].TotalSeconds;
        }
        else
        {
            // use up at least one second of the remaining time, but
            // leave some time for the remaining intervals
            int maxLength = statesTemp[iState].TotalSeconds -
                intervalCounts[iState];
            length = r.Next( 1, maxLength + 1 );
        }

        // keep track of how much time is left to assign for this state
        statesTemp[iState].TotalSeconds -= length;

        // add a new interval
        Interval interval = new Interval();
        interval.State = states[iState].State;
        interval.Date = next;
        interval.Duration = length;
        result.Add( interval );

        // update the start time for the next interval
        next += new TimeSpan( 0, 0, length );
    }

    return result.ToArray();
}

Answer 3

Here is my current implementation that seems to work ok and accounts for all time. This would be so much cleaner if I didn't have to target .net 1.1

public class Interval
{
    public Interval(int state)
    {
     this.State = state;
     this.Duration = -1; 
     this.Date = DateTime.MinValue;
    }
    public DateTime Date;
    public long Duration; 
    public int State; 
}

class StateSummary
{
    public StateSummary(StateEnum state, long totalSeconds)
    { 
     State = (int)state;
     TotalSeconds = totalSeconds;
    }
    public int State;
    public long TotalSeconds; 
}

Interval[] GetRandomIntervals(DateTime start, DateTime end, StateSummary[] sums, int totalEvents)
{
    Random r = new Random(); 
    ArrayList intervals = new ArrayList();

    for (int i=0; i < sums.Length; i++)
    {
     intervals.Add(new Interval(sums[i].State));
    }

    for (int i=0; i < totalEvents - sums.Length; i++)
    {
     intervals.Add(new Interval(sums[r.Next(0,sums.Length)].State));
    }

    Hashtable eventCounts = new Hashtable();
    foreach (Interval interval in intervals)
    {
     if (eventCounts[interval.State] == null) 
     {
      eventCounts[interval.State] = 1; 
     }
     else 
     {
      eventCounts[interval.State] = ((int)eventCounts[interval.State]) + 1;
     }
    }

    foreach(StateSummary sum in sums)
    {
     long avgDuration = sum.TotalSeconds / (int)eventCounts[sum.State];
     foreach (Interval interval in intervals) 
     {
      if (interval.State == sum.State)
      {
       long offset = ((long)(r.NextDouble() * avgDuration)) - (avgDuration / 2); 
       interval.Duration = avgDuration + offset; 
      }
     }
    } 

    // cap the durations. 
    Hashtable eventTotals = new Hashtable();
    foreach (Interval interval in intervals)
    {
     if (eventTotals[interval.State] == null) 
     {
      eventTotals[interval.State] = interval.Duration; 
     }
     else 
     {
      eventTotals[interval.State] = ((long)eventTotals[interval.State]) + interval.Duration;
     }
    }

    foreach(StateSummary sum in sums)
    {
     long diff = sum.TotalSeconds - (long)eventTotals[sum.State];
     if (diff != 0)
     {
      long diffPerInterval = diff / (int)eventCounts[sum.State]; 
      long mod = diff % (int)eventCounts[sum.State];
      bool first = true;
      foreach (Interval interval in intervals) 
      {
       if (interval.State == sum.State)
       {
        interval.Duration += diffPerInterval;
        if (first) 
        {
         interval.Duration += mod;
         first = false;
        }

       }
      }
     }
    }

    Shuffle(intervals);

    DateTime d = start; 
    foreach (Interval interval in intervals) 
    {
     interval.Date = d; 
     d = d.AddSeconds(interval.Duration);
    }

    return (Interval[])intervals.ToArray(typeof(Interval));
}

public static ICollection Shuffle(ICollection c)
{
    Random rng = new Random();
    object[] a = new object[c.Count];
    c.CopyTo(a, 0);
    byte[] b = new byte[a.Length];
    rng.NextBytes(b);
    Array.Sort(b, a);
    return new ArrayList(a);
}