2

我需要每天随机选择 N 个事件，但它们之间不能太接近（M）。因此，N 个事件必须在特定窗口 (W) 内相隔至少 M。在这种情况下，我想到的窗口是 12 小时。

  • N = 事件数
  • T = 事件发生的时间 (UTC)
  • M = 他们应该分开的最小因素（小时）。
  • W = 事件的窗口（现在到现在 + 12 小时）。
  • U = 用户（可能对这个问题不重要）

我可能会弄清楚这一点，但我认为这将是一个有趣的 StackOverflow 问题，并且对人们如何解决它感兴趣。

提前致谢 ：）

更新：将答案移至答案

4

6 回答 6

3

试试这个：

它随机拆分可用时间（窗口计数 * 最小值），然后对时间进行排序并添加最小数量以生成最终事件数组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
    }

作为检查，当最小时间完全覆盖时间窗口时，事件是等距的。因此，对于 12 小时窗口上的 3 个事件，最短时间为 6 小时，该算法按预期在 0.0 、6.0 和 12.0 处产生事件。

于 2013-03-22T19:32:24.220 回答
2

您可以在这里使用我对我的问题的想法：生成非连续组合，本质上要求您只解决 M=0 的情况。

如果你想跳过描述，算法在帖子末尾给出，它没有不可预测的while循环等，并且保证是O（N log N）时间（如果不是的话，本来是O（N）用于排序步骤）。

详细描述

为了将一般的 M 情况简化为 M=0 的情况，我们将每个可能的组合（具有“至少 M 约束”）映射到没有“至少 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
于 2013-03-22T19:06:25.330 回答
1 
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
于 2013-03-22T18:23:37.987 回答
1

如果我们假设事件是瞬时发生的（因此，可以在时间 = 窗口结束时发生，您可以执行以下操作：

//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 小时的窗口中，每个事件在下一个事件之后至少一个小时，你最好有一个小的 N - 我上面的伪代码不会检查是否有可能将 N 个事件放入 X 时间，M 小时之间每个事件。

于 2013-03-22T18:25:56.127 回答
1

首先考虑生成一个事件的工作，这样还有 (n-1) 个事件要生成（每个事件需要至少相隔 M）并且总共剩下 w 时间。

时间 t 可以在 0 到 w-(n-1)m 之间。t 的平均值应为 w/(n-1)。现在，使用任何你喜欢的分布（我推荐泊松）来生成一个均值为 w/(n-1) 的随机数。如果数字大于wn-1)m，则再次生成。那会给你的。

递归调用 (offset=offset+t, w=wt, 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)

我没有为角落条件和其他情况编写代码，我把它留给你。

于 2013-03-22T19:28:36.393 回答
0

这是我的解决方案。如果您分开的时间和 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();
        }
    }
}
于 2013-03-26T15:00:14.660 回答