Как сгенерировать последовательность из n случайных натуральных чисел, которые складываются до некоторого значения?

Я пытаюсь сгенерировать массив целых чисел, содержащий случайные значения, складывающиеся до определенного значения. Вот мой код:

<code>private long[] getRandoms(long size , long sum) throws Exception {
  double iniSum = 0;
  System.out.println("sum = " + sum);
  long[] ret = new long[(int) size];
  for (int i = 0 ; i < ret.length; i++) {
    ret[i] = randomInRange(1, sum);
    iniSum += ret[i];
  }

  double finSum = 0;
  for (int i = 0 ; i < ret.length; i++) {
    ret[i] =  Math.round((sum * ret[i]) / iniSum);
    System.out.println("ret[" + i +"] = " + ret[i]);
    finSum += ret[i];
  }

  if (finSum != sum) throw new Exception("Could not find " + size + " numbers adding up to " + sum  + " . Final sum = " + finSum);
  return ret;
}



private long randomInRange(long min , long max) {
  Random rand = new Random();
  long ret = rand.nextInt((int) (max - min + 1)) + min;
  System.out.println("ret = " + ret);
  return ret;
} 
</code>

Однако результаты не являются точными, например:

Could not find 100 numbers adding up to 4194304 . Final sum = 4194305.0

Я думаю, что теряю точность в этом бите:

<code>(sum * ret[i]) / iniSum
</code>

Можете ли вы порекомендовать альтернативный алгоритм или исправление в моем коде, которое может помочь мне достичь этой цели?

 Andrew Thompson05 апр. 2012 г., 04:16
"I'm trying to generate an array of integers contains randoms adding up to a particular value."  (царапает голову) Не означает ли это, что хотя бы одно из значений в коллекции былоnot random?
 Adam Mihalcin05 апр. 2012 г., 04:15
Выдается ли одно и то же исключение каждый раз, или оно отличается, когда вы запускаете программу более одного раза?
 assylias05 апр. 2012 г., 04:17
@ AndrewThompson Хорошо посмеялся!
 Reverend Gonzo05 апр. 2012 г., 04:23
Что бы ни стоило, модульные тесты не должны иметь случайного поведения. Они должны иметь специально разработанное поведение для проверки конкретного случая.
 BlueRaja - Danny Pflughoeft06 апр. 2012 г., 18:08
@QuantumMechanic: принимаяn случайные числа(in any range, as long as the distribution is uniform)суммирование их и деление их на сумму является стандартным способом генерацииn случайный "честный" числа от[0,1] с суммой 1. Должно быть очевидно, что все они умножаются на другое число.k дам тебеn случайный "честный" числа от[0,k].

Ответы на вопрос(10)

Да, есть стандартный способ сделать это, чтобы избежать неточностей с плавающей точкой. Это связано с методомсчитая количество способов дляn numbers to sum to s, Это не сложно, но, как ни странно, никто еще не упомянул об этом, так что здесь идет:

Представьте, что у нас есть строка сn-1 Х в этом иs O & APOS; с. Так, например, для s = 5, n = 3, одна строка примера будет

oXooXoo

Заметьте, что X делят «o» на три различные группы: одну из длины 1, длины 2 и длины 2. Это соответствует решению [1,2,2]. Каждая возможная строка дает нам другое решение, подсчитывая количество сгруппированных вместе(a 0 is possible: for example, XoooooX would correspond to [0,5,0]).

Итак, все, что нам нужно сделать, это представить себе создание такой строки, выбирая случайные позиции дляn-1 X ', затем выясните, какому решению это соответствует. Вот более подробная разбивка:

Generate n-1 unique random numbers between [1, s+n-1]. Doing this is simple enough with rejection sampling - if a number is chosen twice, just drop it and pick another one. Sort them, then figure out the number of o's between each X. This number turns out to be currentValue - previousValue - 1.

И наконец, вот несколько примеров Java (не проверено), которые должны сделать это:

private List<long> getRandomSequenceWithSum(int numValues, long sum)
{
    List<long> xPositions = new List<long>();
    List<long> solution = new List<long>();
    Random rng = new Random();

    //Determine the positions for all the x's
    while(xPositions.size() < numValues-1)
    {
        //See https://stackoverflow.com/a/2546186/238419
        //for definition of nextLong
        long nextPosition = nextLong(rng, sum+numValues-1) + 1; //Generates number from [1,sum+numValues-1]
        if(!xPositions.contains(nextPosition))
            xPositions.add(nextPosition);
    }

    //Add an X at the beginning and the end of the string, to make counting the o's simpler.
    xPositions.add(0);
    xPositions.add(sum+numValues);
    Collections.sort(xPositions);

    //Calculate the positions of all the o's
    for(int i = 1; i < xPositions.size(); i++)
    {
        long oPosition =  xPositions[i] - xPositions[i-1] - 1;
        solution.add(oPosition);
    }

    return solution;
}
 09 апр. 2012 г., 04:57
Вы можете избежать необходимости использовать выборку отклонения (которая в некоторых случаях становится очень неприятной), разделяя интервалы (в вашем случае выполняется & quot; o & quot; s), взвешивая выбор интервала по числу внутренних границ o-o. (Например, если вы делите свою сумму следующим образом ooooXoXoo У вас есть 3 интервала: первый с весом 3, второй с весом 0 и третий с весом 1. Таким образом, выбрав число от 1 до 4, вы сможете выбрать место для сплит (это в основном метод, который я обрисовал в своем ответе выше).

Предложения:

  for (int i = 0 ; i < ret.length; i++) {
    ret[i] = randomInRange(1, sum);
    iniSum += ret[i];
  }

В первом цикле for вместо итерации от 0 до (ret.length-1) используйте итерации только от 0 до (ret.length-2). Сохраните последний элемент для корректировки.

Также не вызывайте randomInRange (1, sum), используйте взамен randomInRange (1, sum-iniSum). Это уменьшит требуемую нормализацию.

В конце концов, последний выходной номер будет (sum-iniSum). Таким образом, второй цикл for может быть удален.

Я считаю, что ваша проблема связана сMath.round попробуйте изменить ваш код, чтобы использовать удвоения и избежать потери точности

Это, конечно, интересный вопрос (upvote!), И я с нетерпением жду появления более креативных решений. Одна проблема, с которой у меня есть код, который вы перечислили, заключается в том, что вы используетеRandom класс, который возвращает только целые числа, а не long, но тогда вы просто приводите его к long. Поэтому, если вашей функции действительно нужны длинные значения, вам нужно будет найти другой генератор случайных чисел.

"Идеал" Решением было бы создать все возможные аддитивные комбинации (называемые разделами), а затем выбрать одну случайным образом. Однако самые известные алгоритмы для этого действительно очень дороги. Существует много хороших исходных материалов по этой проблеме. Здесь особенно хорошо читаются алгоритмы разбиения:

http://www.site.uottawa.ca/~ivan/F49-int-part.pdf

Частично проблема заключается в выяснении того, что вы подразумеваете под «случайным» в этом случае. Например, если вы ищете массив из 5 чисел, сумма которых равна 1000, {1000,0,0,0,0} так же действует, как {200,200,200,200,200}, что так же верно, как {136,238,124,66,436} , Алгоритм, который имеет равную вероятность генерации любого из этих наборов, будет действительно случайным.

Однако я предполагаю, что вы ищете не полностью случайное распределение, а нечто среднее.

К сожалению, моя Java довольно ржавая, и я делаю почти все в C # в эти дни, поэтому я представлю ее в C # ... не нужно слишком много переводить, чтобы преобразовать эти алгоритмы в Java.

Вот мое мнение о проблеме:

public int[] GetRandoms( int size, int sum, Random r=null ) {
  if( r==null ) r = new Random();
  var ret = new int[size];
    while( sum > 0 ) {
      var n = r.Next( 1, (int)Math.Ceiling((double)sum/size)+1 );
      ret[r.Next(size)] += n;
      sum -= n;
    }
    return ret;
}

(Из практического замечания смотрите, как я передаю свой генератор случайных чисел?null и просто создаю новый для удобства, но теперь я могу передать в генератор случайных чисел с сеяными числами и, если пожелаю, сгенерировать те же результаты, что отлично подходит для целей тестирования. Всякий раз, когда у вас есть метод, который использует генератор случайных чисел, я настоятельно рекомендую использовать этот подход.)

Этот алгоритм в основном продолжает добавлять случайные числа к случайным элементам в массиве, пока сумма не будет достигнута. Из-за своей аддитивной природы он будет отдавать предпочтение большим числам (то есть маловероятно, что в результате появятся малые числа). Тем не менее, числа будут казаться случайными, и они будут суммироваться соответствующим образом.

Если ваше целевое число мало (скажем, до 100), вы действительно можете достичь истинно случайного подхода - сгенерировать все разделы и просто выбрать один наугад. Например, вот алгоритм разделения (любезно предоставленоhttp://homepages.ed.ac.uk/jkellehe/partitions.php, переведено на C #):

public List<int[]> GetPartitions( int n ) {
var result = new List<int[]>();
var a = new int[n+1];
var k = 1;
a[0] = 0;
var y = n - 1;
while( k != 0 ) {
    var x = a[k-1] + 1;
    k--;
    while( 2*x <= y ) {
        a[k] = x;
        y -= x;
        k++;
    }
    var l = k + 1;
    while( x <= y ) {
        a[k] = x;
        a[l] = y;
        result.Add( a.Take( k + 2 ).ToArray() );
        x++;
        y--;
    }
    a[k] = x + y;
    y = x + y - 1;
    result.Add( a.Take( k + 1 ).ToArray() );
}
return result;
}

(Чтобы помочь вам в переводе Java,a.Take(x) значит взять первыйx элементы из массиваa... Я уверен, что в наши дни в Java существует некая эквивалентная магия.)

Это возвращает список разделов ... просто выберите один наугад, и вы получите идеальное случайное распределение.

-Как насчет этого?

private long[] getRandoms(int size , long sum) {
    long[] array = new long[size];
    long singleCell = sum / size;
    Arrays.fill(array, singleCell);
    array[size-1] += sum % singleCell;
    int numberOfCicles = randomInRange(size, size*10);
    for (int i = 0; i < numberOfCicles; i++) {
        int randomIndex = randomInRange(0, size);
        long randomNumToChange = randomInRange(0, array[randomIndex]);
        array[randomIndex] -= randomNumToChange;
        array[randomInRange(0, size)] += randomNumToChange;
    }
    return array;
}

Как насчет этого:

long finSum = 0;
for (int i = 0 ; i < ret.length; i++) {
  ret[i] =  Math.round((sum * ret[i]) / iniSum);
  System.out.println("ret[" + i +"] = " + ret[i]);
  finSum += ret[i];
}
ret[0] += sum - finSum;

Другими словами, поместите все ошибки округления в первый элемент.

Возьми номер. Вычтите из него разумное случайное число. Повторяйте, пока не наберете достаточно цифр. Их сумма по определению фиксирована и равна начальному числу. Вы делаете именноn операции, гдеn количество нужных вам чисел; не гадать.

Вот код Python:

import random
def generate_randoms(initial, n):
  # generates n random numbers that add up to initial.
  result = [] # empty list
  remainder = initial # we'll subtract random numbers and track the remainder
  numbers_left = n
  while numbers_left > 1:
    # guarantee that each following step can subtract at least 1
    upper_bound = remainder - numbers_left 
    next_number = random.randrange(1, upper_bound) # [1, upper_bound) 
    result.append(next_number)
    remainder -= next_number # chop off
    numbers_left -= 1
  result.append(remainder) # we've cut n-1 numbers; don't forget what remains
  return result

Это работает, но у него есть и обратная сторона: чем дальше цифры, тем они меньше. Возможно, вам придется перетасовать полученный список, чтобы бороться с этим, или играть с меньшими верхними границами.

Решение Вопроса

Каждый раз, когда вы масштабируете значение сret[i] = Math.round((sum * ret[i]) / iniSum), вы потеряете некоторую точность, частично из-за самой операции деления, но в основном из-за сохранения масштабированного значения в виде целого числа. Более поздняя ситуация аналогична пропорциональным избирательным системам, где небольшое количество мест должно быть выделено пропорционально большему количеству голосов.

Два метода для смягчения этого:

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

long finSum = 0;  // Might as well be a long
float[] idealValues = new float[size];
for (int i = 0 ; i < ret.length; i++) {
    ideal[i] = (sum * ret[i]) / iniSum;
    ret[i] = (long) (ideal[i]);  // Truncate, not round
    System.out.println("ret[" + i +"] = " + ret[i]);
    finSum += ret[i];
}

/* There are iniSum - finSum extra amounts to add. */
for (int i = 0; i < iniSum - finSum; i++)
{
    /* Pick a target slot to increment.  This could be done by keeping a priority queue. */
    int target = 0;
    float bestScore = 0.0;
    for (int j = 0; j < size; j++) {
        float score = (ideal[j] - ret[j])/ret[j];
        if (score > bestScore) {
            target = j;
            bestScore = score;
        }
    }

    /* Allocate an additional value to the target. */
    ret[target]++;
}

Или, проще говоря, вы можете просто установить последнее значение в списке на то, что является выдающимся после масштабирования, выполняя все остальные. Это статистически искажает вывод, однако.

 05 апр. 2012 г., 04:55
Мне нравится такой подход, однако вы могли бы просто выпустить эту дополнительную сумму, выбрав случайный слот. Я не думаю, что это повлияет на распределение хуже, чем существующий метод.
 06 апр. 2012 г., 20:44
Это решение смягчает проблему неточности с плавающей точкой, но не устраняет ее. Существуют решения, которые вообще не зависят от числа с плавающей точкой, такие как @woodings или мой ответ.

Хороший метод - работать со списком интервалов, которые вы затем разбиваете на каждом шаге. Здесь псевдокод

 array intervals = [(0,M)]
   while number intervals<desired_number
     pick an split point x
     find the interval containing x
     split that interval at x

Если вы хотите быть очень осторожным, вам нужно убедиться, что ваша точка разделения x не является конечной точкой интервала. Вы можете сделать это путем отклонения, или вы можете выбрать интервал для разделения, затем, где разделить этот интервал, но в этом случае вы должны быть осторожны, чтобы не вносить смещение. (Если вам небезразлична предвзятость).

Просто есть идея. Инициализируйте массив для всех 0. Случайно выберите число в массиве и увеличьте на 1 и уменьшите сумму на 1, пока сумма не станет 0. Это не практично, когда сумма велика :)

long ret = new long[size];
for(int i=0;i<size;i++) ret[i]=0;
for(int i=0;i<sum;i++) {
  int n = random(0,size);
  ret[n]++;
}
 05 апр. 2012 г., 04:38
Это имеет преимущество быть беспристрастным, но недостатком является медлительность.
 05 апр. 2012 г., 04:43
Модификация этого состоит в том, чтобы разделить число поровну (или почти полностью) на N частей, а затем многократно выбирать две части случайным образом и сдвигать некоторые значения между ними. Вроде как тасование. Я не уверен, сколько вам нужно перетасовать, чтобы получить что-то действительно случайное. Вы могли бы также сделать это, сдвигая постепенно уменьшающиеся суммы примерно слишком ... начинайте с большого, а работайте с маленьким ... это может дать лучшее распределение чисел.

Ваш ответ на вопрос