Это старый вопрос, но я обнаружил, что искал решение этой проблемы для практического использования в приложении для генерации случайных данных.
Основываясь на идеях в этом посте, я предложил два возможных решения.
Первый метод:
- Определите наименьшее целочисленное значение, которое можно повторить, чтобы сложить число рядом с желаемой суммой. По сути, просто делите целочисленное деление.
- Инициализировать массив со всеми значениями, равными числу, найденному на шаге 1.
- Если есть остаток (как правило, будет), случайным образом добавьте его к элементам в массиве и уменьшайте его до тех пор, пока остаток не станет равным 0. В этот момент у нас есть массив, который будет равен желаемому итогу, но он будет быть очень неслучайным.
- Для ряда итераций случайным образом складывайте и вычитайте из двух мест в массиве. Пример: добавьте 1 в позицию 0 и вычтите 1 из позиции 4. При этом выполните проверку границ (все числа должны быть не менее 0, а все числа не должны превышать верхнюю границу).
Второй метод намного проще, но приводит к менее случайному распределению:
- Инициализировать массив из 0 требуемой длины.
- Выберите случайный индекс в массиве и добавьте 1. Если значение этого индекса превысит верхнюю границу, проигнорируйте его и выберите другой индекс.
- Повторите шаг 2 количество раз, указанное нужной суммой.
Вот код:
public static int[] getRandomsWithTotalA(int desiredTotal, int desiredNumbers, int upperBound)
{
Random r = new Random();
// Is this even a possible feat?
if (desiredNumbers * upperBound < desiredTotal) throw new ArgumentException("This is not possible!", "desiredTotal");
// Start by figuring out the closest number we can get to by repeating the initial number.
int lowestRepeating = desiredTotal / desiredNumbers;
// Determine the remainder
int lowestRepeatingRemainder = desiredTotal % desiredNumbers;
// Initialize and populate an array of numbers with the lowest repeater.
int[] results = Enumerable.Repeat(lowestRepeating, desiredNumbers).ToArray();
// We will perform (n*desiredTotal) shuffles.
int shuffles = (desiredTotal * desiredNumbers);
while (shuffles > 0)
{
int a = r.Next(desiredNumbers);
int b= r.Next(desiredNumbers);
if (a==b) continue; // do nothing if they're equal - try again.
// Test bounds.
if (results[a]+1>upperBound) continue;
if (results[b]-1<0) continue;
// Add one to the first item.
results[a]++;
// Do we still have a remainder left? If so, add one but don't subtract from
// somewhere else.
if (lowestRepeatingRemainder>0)
{
lowestRepeatingRemainder--;
continue;
}
// Otherwise subtract from another place.
results[b]--;
// decrement shuffles
shuffles--;
}
return results;
}
public static int[] getRandomsWithTotalB(int desiredTotal, int desiredNumbers, int upperBound)
{
Random r = new Random();
// Is this even a possible feat?
if (desiredNumbers * upperBound < desiredTotal) throw new ArgumentException("This is not possible!", "desiredTotal");
// Initialize and populate an array of numbers with the lowest repeater.
int[] results = new int[desiredNumbers];
while (desiredTotal > 0)
{
int a = r.Next(desiredNumbers);
// Test bounds.
if (results[a] + 1 > upperBound) continue;
// Add one to the first item.
results[a]++;
desiredTotal--;
}
return results;
}
Пример прогона:
static void Main(string[] args)
{
foreach (int i in getRandomsWithTotalA(200, 30, 9))
{
Console.Write("{0}, ", i);
}
Console.WriteLine("\n");
foreach (int i in getRandomsWithTotalB(200, 30, 9))
{
Console.Write("{0}, ", i);
}
}
3, 8, 7, 5, 9, 9, 8, 9, 9, 6, 8, 7, 4, 8, 7, 7, 8, 9, 2, 7, 9, 5, 8, 1, 4, 5, 4, 8, 9, 7,
6, 8, 5, 7, 6, 9, 9, 8, 5, 4, 4, 6, 7, 7, 8, 4, 9, 6, 6, 5, 8, 9, 9, 6, 6, 8, 7, 4, 7, 7,
Понятно, что эти методы распределены не так равномерно, как хотелось бы. Это имело бы смысл, особенно со вторым методом; если у вас есть случайный источник, который действительно равномерно распределен, то ваш выбор элементов для увеличения должен иметь равную вероятность по всем возможным значениям. Первый также может быть немного лучше, но он все еще страдает от того факта, что случайный источник также идеально распределен равномерно.
Мне кажется, что возможно улучшить хотя бы первый метод, введя некоторую форму смещения в выбор индекса, или, возможно, рандомизировать то, сколько мы добавляем и вычитаем (не всегда 1), или рандомизировать, мы на самом деле делаем сложение / вычитание или нет. Кажется, простое изменение количества итераций меняет распределение, но через некоторое время мы начинаем отдавать предпочтение внешним границам. (Возможно, невозможно получить по-настоящему равномерный дистрибутив!)
В любом случае, вы идете ... Хорошее место, чтобы начать хотя бы.