1 日に N 個のイベントをランダムに選択する必要がありますが、互いに近すぎることはできません (M)。したがって、N 個のイベントは、特定のウィンドウ (W) 内で少なくとも M 個離れている必要があります。この場合、私が考えているウィンドウは 12 時間です。
私はおそらくこれを理解することができましたが、それは楽しい StackOverflow の質問であり、人々がどのように解決するのかに興味がありました。
前もって感謝します ：）
更新: 回答を回答に移動しました
これを試して：
利用可能な時間 (ウィンドウ数 * 最小値) をランダムに分割し、時間を並べ替えて最小量を追加し、最終的なイベント配列を生成し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
}
チェックとして、最小時間が時間枠を完全にカバーする場合、イベントは等間隔で配置されます。したがって、最小時間が 6 時間の 12 時間のウィンドウでの 3 つのイベントの場合、このアルゴリズムは予想どおり 0.0、6.0、および 12.0 でイベントを生成します。
ここで私の質問に対して私が持っていたアイデアを使用できます: Generating non-consecutive compilation、基本的に 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
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
イベントが瞬時に発生すると仮定した場合 (つまり、時間 = ウィンドウの終わりに発生する可能性がある場合)、次のようにすることができます。
//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);
}
}
さて、各イベントの少なくとも 1 時間後に次のイベントが発生する 12 時間枠では、N を小さくするのが最適です。上記の擬似コードでは、N イベントを X 時間に合わせて M 時間間隔で収まるかどうかを確認しません。各イベント。
最初に、生成するイベントが (n-1) 個以上あり (それぞれ少なくとも M ずつ区切る必要がある)、残りの合計時間が w になるように、1 つのイベントを生成するジョブを考えます。
時間 t は、0 から w-(n-1)m の間で指定できます。t の平均値は w/(n-1) である必要があります。ここで、お気に入りの分布 (ポアソンをお勧めします) を使用して、平均 w/(n-1) の乱数を生成します。数が wn-1)m より大きい場合は、再度生成します。それはあなたのtを与えるでしょう。
(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)
コーナー条件やその他のケースについてはコーディングしていませんので、お任せします。
これが私の解決策です。離れた時間と 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();
}
}
}