У меня есть значение, скажем, 20010. Я хочу случайным образом разделить это значение в течение 24 часов. Таким образом, в основном разделить значение на 24-сегментный большой массив, где все слоты случайным образом большие.
Что может быть хорошим способом решить это с помощью С#?
Нарисуйте 23 (не 24) числа в случайном порядке (без дубликатов) в диапазоне от 1 до 20009. Добавьте 0 и 20010 список и упорядочите эти цифры, разница между двумя последовательными номерами даст вам одно значение слота.
Онлайн-подход также возможен, вытягивая по одному значению за раз и вычитая его из "банка", рисуя заново, когда число больше оставшейся суммы. Однако этот подход может привести к большему отклонению размеров слотов.
Здесь существует функциональное решение с использованием алгоритма mjv:
static int[] GetSlots(int slots, int max)
{
return new Random().Values(1, max)
.Take(slots - 1)
.Append(0, max)
.OrderBy(i => i)
.Pairwise((x, y) => y - x)
.ToArray();
}
public static IEnumerable<int> Values(this Random random, int minValue, int maxValue)
{
while (true)
yield return random.Next(minValue, maxValue);
}
public static IEnumerable<TResult> Pairwise<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TSource, TResult> resultSelector)
{
TSource previous = default(TSource);
using (var it = source.GetEnumerator())
{
if (it.MoveNext())
previous = it.Current;
while (it.MoveNext())
yield return resultSelector(previous, previous = it.Current);
}
}
public static IEnumerable<T> Append<T>(this IEnumerable<T> source, params T[] args)
{
return source.Concat(args);
}
Предполагая, что вы не хотите иметь большого (любого) контроля над распределением размеров, вот подход, который будет работать (псевдокод).
Примечания
Это весело. Вдохновленный Дэвидом, здесь реализовано решение mjv с использованием только операторов, предоставляемых LINQ. Поскольку ключ David Dictionary является просто индексом, мы можем использовать массив для функции Pairwise:
var r = new Random();
var a = Enumerable.Repeat(null, n - 1) // Seq with (n-1) elements...
.Select(x => r.Next(1, m)) // ...mapped to random values
.Concat(new [] { 0, m })
.OrderBy(x => x)
.ToArray();
return a.Skip(1).Select((x,i) => x - a[i]);
Я вычислил средний размер каждого из 24 ведер более чем 100 испытаний для каждого из предложенных здесь алгоритмов. Я подумал, что интересно, что три из четырех, кажется, приводят в среднем к 20010/24 предметам на ведро в среднем, но наивный метод, который я описал, сходится к этому среднему наиболее быстро. Это делает меня интуитивным. Этот метод похож на снег случайно на 24 ведрах и, следовательно, может привести к тому, что они будут примерно равны по размеру. Другие больше похожи на хакерство в случайном порядке по длине дерева.
Bevan: [751, 845, 809, 750, 887, 886, 838, 868, 837, 902, 841, 812, 818, 774, 815, 857, 752, 815, 896, 872, 833, 864, 769, 894]
Gregory: [9633, 5096, 2623, 1341, 766, 243, 159, 65, 21, 19, 16, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
mjv: [895, 632, 884, 837, 799, 722, 853, 749, 915, 756, 814, 863, 842, 642, 820, 805, 659, 862, 742, 812, 768, 816, 721, 940]
peterallenwebb: [832, 833, 835, 829, 833, 832, 837, 835, 833, 827, 833, 832, 834, 833, 836, 833, 838, 834, 834, 833, 834, 832, 836, 830]
И вот код python: import random
N = 20010;
def mjv():
gaps = [ random.randrange(0, N) for i in range(0, 24) ]
gaps = gaps + [0, N]
gaps.sort()
value = [ gaps[i+1] - gaps[i] for i in range(0, 24) ]
return value
def gregory():
values = []
remainingPortion = N
for i in range(0, 23):
val = random.randrange(1, remainingPortion - (23 - i))
remainingPortion = remainingPortion - val
values.append(val)
values.append(remainingPortion)
return values
def peterallenwebb():
values = [0 for i in range(0, 24) ]
for i in range(0, N):
k = random.randrange(0, 24)
values[k] = values[k] + 1
return values
def bevan():
values = [];
sum = 0.0
for i in range(0, 24):
k = random.random()
sum = sum + k
values.append(k);
scaleFactor = N / sum
for j in range(0, 24):
values[j] = int(values[j] * scaleFactor)
return values
def averageBucketSizes(method):
totals = [0 for i in range(0, 24)]
trials = 100
for i in range(0,trials):
values = method()
for j in range(0, 24):
totals[j] = totals[j] + values[j]
for j in range(0, 24):
totals[j] = totals[j] / trials
return totals;
print 'Bevan: ', averageBucketSizes(bevan)
print 'Gregory: ', averageBucketSizes(gregory)
print 'mjv: ', averageBucketSizes(mjv)
print 'peterallenwebb: ', averageBucketSizes(peterallenwebb)
Сообщите мне, видите ли вы какие-либо ошибки. Я снова запустил.
Если вы хотите быть уверенным, что вы не смещаете процесс без особого анализа, вы можете просто создать массив из 24 элементов, инициализировать каждый элемент до 0 и затем добавить один к одному из элементов произвольно 20010 раз.
Все зависит от вида дистрибутивов, которые вы хотите увидеть, но я не думаю, что какие-либо другие рекомендации, рекомендуемые до сих пор, приведут к тому, что часовые "ведра" будут статистически неразличимы.
Другой вариант - создать случайное число между 0 и целевым номером. Затем добавьте каждую "кусок" в список. Выберите самый большой "кусок" и разделите его на две части, используя другое случайное число. Выберите самый большой из списка (теперь с тремя частями) и продолжайте, пока не получите желаемое количество штук.
List<int> list = new List<int>();
list.Add(2010);
Random random = new Random();
while (list.Count() < 24)
{
var largest = list.Max();
var newPiece = random.Next(largest - 1);
list.Remove(largest);
list.Add(newPiece);
list.Add(largest - newPiece);
}
Здесь другое решение, которое, я думаю, будет очень хорошо работать для этого. Каждый раз, когда вызывается метод, он возвращает другой набор случайно распределенных значений.
public static IEnumerable<int> Split(int n, int m)
{
Random r = new Random();
int i = 0;
var dict = Enumerable.Range(1, m - 1)
.Select(x => new { Key = r.NextDouble(), Value = x })
.OrderBy(x => x.Key)
.Take(n - 2)
.Select(x => x.Value)
.Union(new[] { 0, m })
.OrderBy(x => x)
.ToDictionary(x => i++);
return dict.Skip(1).Select(x => x.Value - dict[x.Key - 1]);
}
Это даст вам несколько "уменьшающуюся" случайность, чем выше индекс. Вы можете рандомизировать позиции списка, если это необходимо? Это зависит от того, что вам нужно с этим делать.
int initialValue = 20010;
var values = new List<int>();
Random rnd = new Random();
int currentRemainder = initialValue;
for (int i = 0; i < 21; i++)
{
//get a new value;
int val = rnd.Next(1, currentRemainder - (21 - i));
currentRemainder -= val;
values.Add(val);
}
values.Add(currentRemainder);
//initialValue == values.Sum()
class Numeric
def n_rands(n)
raw = (1..n).map { |x| rand }
raw.map { |x| x * to_f / raw.sum.to_f }.map { |x| x.to_i }.tap do |scaled|
scaled[-1] = self - scaled[0..-2].sum
end
end
end
puts 1000.n_rands(10).inspect # [22, 70, 180, 192, 4, 121, 102, 179, 118, 12]
Я попробовал решения от Дэвида и Далбыка, но не повезло. Итак, вот что я придумал после прочтения ответа от mjv:
public static class IntExtensions
{
public static IEnumerable<int> Split(this int number, int parts)
{
var slots = Enumerable.Repeat(0, parts).ToList();
var random = new Random();
while (number > 0)
{
var slot = random.Next(0, parts);
slots[slot]++;
number--;
}
return slots;
}
}