Получение случайных длительностей в диапазоне в C #

Question

Для генератора случайных событий, который я пишу, мне нужен простой алгоритм для генерации случайных диапазонов.

Так, например:

Я могу сказать, что я хочу 10 случайных интервалов, между 1/1 и 1/7, без наложения, в состояниях (1,2,3), где события состояния 1 суммируются до 1 дня, события состояния 2 суммируются до 2 дней и укажите 3 события в сумме с остальными.

Или в коде:

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 
}

Я сейчас работаю над этим, но в случае, если кто-то превзойдет меня в решении (или знает элегантный ранее существующий алгоритм), я публикую это на SO.

Answer 1

Сначала используйте DateTime.Subtract, чтобы определить, сколько минут / секунд / что угодно между вашими минимальными и максимальными датами. Затем используйте Math.Random, чтобы получить случайное количество минут / секунд / что угодно в этом диапазоне. Затем используйте результат этого для создания другого экземпляра TimeSpan и добавьте его к вашему минимальному DateTime.

Answer 2

Вот моя текущая реализация, которая, кажется, работает нормально и учитывает все время. Это было бы намного чище, если бы мне не нужно было нацеливаться на .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);
}

Answer 3

Вот реализация, которая компилируется и работает, хотя она все еще несколько грубая. Требуется, чтобы массив входных состояний правильно учитывал весь интересующий диапазон времени (конец - начало), но было бы тривиально добавить немного кода, который заставил бы конечное состояние заполнять время, не учитываемое в первом N -1 шт. Я также изменил определения вашей структуры, чтобы использовать целые числа вместо длинных для длительностей, просто чтобы немного упростить ситуацию.

Для ясности (и лени) я пропустил все проверки ошибок. Он отлично работает для входов, подобных тем, которые вы описали, но ни в коем случае не пуленепробиваемый.

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();
}