Алгоритм выбора случайных времен в окне на пользователя

Question

Мне нужно выбрать N количество событий в день случайным образом, но они не могут быть слишком близки друг к другу (M). Таким образом, N событий должно быть по крайней мере M в отдельном окне (W). В этом случае окно, о котором я думаю, составляет 12 часов.

• N = число событий
• T = время, в которое должно произойти событие (UTC)
• M = минимальный коэффициент они должны быть друг от друга (часы).
• W = окно событий (теперь на данный момент + 12 часов).
• U = пользователь (вероятно, не имеет значения для этой проблемы)

Я мог бы понять это, но я думал, что это будет весело StackOverflow вопрос и интересует, как люди будут решить.

Заранее спасибо :)

Update: Перемещенные ответ на ответ

Answer 1

Попробуйте это:

Он делит доступное время (окно - счетчик * минимум) случайным образом, а затем сортирует раз и добавляет минимальное количество, чтобы произвести окончательный массив событий T[].

static Random rnd=new Random(); 

    static void Main(string[] args) 
    { 
     double W=12; 
     double M=1.0; 

     int N=7; 

     double S=W-(N-1)*M; 
     double[] T=new double[N]; 

     for(int i=0; i<N; i++) 
     { 
      T[i]=rnd.NextDouble()*S; 
     } 
     Array.Sort(T); 
     for(int i=0; i<N; i++) 
     { 
      T[i]+=M*i; 
     } 

     Console.WriteLine("{0,8} {1,8}", "#", "Time"); 
     for(int i=0; i<N; i++) 
     { 
      Console.WriteLine("{0,8} {1,8:F3}", i+1, T[i]);  
     } 

     // With N=3, Window 12h, Min. Span = 5h 
     //  #  Time 
     //  1 0.468 
     //  2 5.496 
     //  3 10.529 

     // With N=7, Window 12h, Min. Span = 1h 
     //  #  Time 
     //  1 0.724 
     //  2 2.771 
     //  3 4.020 
     //  4 5.790 
     //  5 7.331 
     //  6 9.214 
     //  7 10.673 
    } 

В качестве проверки также, когда минимальное время полностью закрывает окно времени, события равномерно распределены. Таким образом, для 3-х событий в 12-часовом окне с минимальным временем 6 часов этот алгоритм производит события на 0.0, 6.0 и 12.0, как и ожидалось.

Answer 2

timeItems = new List(); 
int range; 
double randomDouble; 

for i = 1 to N 
{ 
    range = W/M; 

    //assumes generate produces a random number between 0 and 1 (exclusive) 
    randomDouble = RandomGenerator.generate() * (range); 
    T = Math.floor(randomDouble)*M; 
    timeItems.add(T); 
} 

return timeItems 

Answer 3

Если предположить, что события происходят мгновенно (и, таким образом, может произойти в момент времени = конец окна , вы могли бы сделать что-то вроде этого:

//Using these, as defined in the question 
double M; 
int N; 
DateTime start; //Taken from W 
DateTime end; //Taken from W 

//Set these up. 
Random rand = new Random(); 
List<DateTime> times; 
//This assumes that M is 
TimeSpan waitTime = new TimeSpan.FromHours(M); 
int totalSeconds = ((TimeSpan)end-start).TotalSeconds; 

while(times.Count < N) 
{ 
    int seconds = rand.Next(totalSeconds); 
    DateTime next = start.AddSeconds(seconds); 
    bool valid = true; 
    if(times.Count > 0) 
    { 
     foreach(DateTime dt in times) 
     { 
      valid = (dt > next && ((TimeSpan)dt - next) > waitTime) ? true : false; 
      if(!valid) 
      { 
       break; 
      } 
     } 
    } 
    if(valid) 
    { 
     times.Add(next); 
    } 
} 

Теперь, в 12 часов окна, по крайней мере в течение часа после каждого события до следующего, года u'd лучше иметь маленький N - мой psuedocode выше, не проверяет, можно ли поместить N событий в X время с M часами между каждым событием.

Answer 4

Вы можете использовать идею, которую я имел для моего вопроса здесь: Generating non-consecutive combinations, по сути, требуя, чтобы вы разрешили только случай M = 0.

Если вы хотите пропустить описание, алгоритм будет указан в конце сообщения, который не имеет непредсказуемых циклов и т. Д., И гарантированно будет O (N log N) времени (было бы O (N), если не для этапа сортировки).

---

Long Описание

Для того, чтобы уменьшить общий М случай к М = 0 случае, каждой из возможных комбинаций (с «aleast М ограничение») в комбинации без «по крайней мере, M ".

Если события были в T1, T2, .., TN таким образом, что T1 <= T2 -M, T2 <= T3 - M ... вы сопоставить их с событиями Q1, Q2, .. QN таким образом, что

Q1 = T1 
Q2 = T2 - M 
Q3 = T3 - 2M 
... 
QN = TN - (N-1)M. 

Эти Q удовлетворяют свойству, что Q1 <= Q2 <= ... <= QN, а отображение 1 к 1. (С T вы можете построить Q, а с Q вы можете построить T).

Итак, все, что вам нужно сделать, это сгенерировать Q (что по существу является корпусом M=0) и отобразить их обратно на T.

Обратите внимание, что окно для создания Q становится [Now, Now+12 - (N-1)M]

Для решения M=0 проблемы, просто генерировать N случайных чисел в окне и сортировать их.

---

Окончательный алгоритм

Таким образом, весь ваш алгоритм будет

Step 1) Set Window = [Start, End - (N-1)M] 
Step 2) Generate N random numbers in the Window. 
Step 3) Sort the numbers generated in Step 2. Call them Q1, Q2, .. , QN 
Step 4) Create Ti with the formula Ti = Qi + (i-1)M, for i = 1 to N. 
Step 5) Output T1,T2,..,TN 

Answer 5

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

Время t может находиться в диапазоне от 0 до w- (n-1) m. Среднее значение t должно быть w/(n-1). Теперь используйте любой из ваших любимых дистрибутивов (я рекомендую poisson) для генерации случайного числа со средним значением w/(n-1). Если число больше, чем w-n-1) m, затем генерируйте снова. Это даст вам т.

Рекурсивно вызывать (смещение = смещение + t, w = w-t, n = n-1, m = m) для генерации большего числа чисел.

def generate(offset, w, n, m): 
    mean = w/(n-1); 
    t=ininity; 
    while (t> (w-(n-1)m)): 
     t= poisson(w/(n-1)) 
    return [t+offset] + generate(offset+t, w-t, n-1, m) 

Я не кодировал угловые условия и другие случаи, которые я оставляю вам.

Answer 6

вот мое решение. Вы получаете какое-то странное поведение, если ваше время в стороне и numOfEvents противоречивы. Поиграйте с ним и посмотрите, что произойдет.

using System; 
using System.Collections.Generic; 

namespace RandomScheduler 
{ 
    class Program 
    { 
     public static Random R = new Random(); 

     static void Main() 
     { 
      var now = DateTime.Now; 
      var random = new Random((int)now.Ticks); 
      const int windowOfHours = 12; 
      const int minimumTimeApartInHours = 2; 
      const int numOfEvents = 5; 

      // let's start the window 8 AM 
      var start = new DateTime(now.Year, now.Month, now.Day, 8, 0, 0, 0); 
      // let's end 12 hours later 
      var end = start.AddHours(windowOfHours); 

      var prev = null as DateTime?; 
      const int hoursInEachSection = windowOfHours/numOfEvents; 

      var events = new List<DateTime>(); 

      for (var i = 0; i < numOfEvents; i++) 
      { 
       // if there is a previous value 
       // let's at least start 2 hours later 
       if (prev.HasValue) 
        start = prev.Value.AddHours(minimumTimeApartInHours); 

       DateTime? @event; 
       do 
       { 
        // pick a random double, so we get minutes involved 
        var hoursToAdd = random.NextDouble()*hoursInEachSection; 
        // let's add the random hours to the start 
        // and we get our next event 
        @event = start.AddHours(hoursToAdd); 

       // let's make sure we don't go past the window 
       } while (@event > end); 

       prev = @event; 
       events.Add(@event.Value); 
      } 

      Console.WriteLine(string.Join("\n", events)); 
      Console.ReadLine(); 
     } 
    } 
}