Равномерно разделить `n` двойных чисел на общую сумму `s`, где каждое двойное число меньше 1 (при правильном выполнении)

В настоящее время я работаю над этой задачей (код-гольф), и мне трудно совмещать четыре требования, заданные целым числом n и общей десятичной суммой s (учитывая диапазоны, которые мы должны поддерживать: 1 <= n <= 10 и 0 <= s <= n):

  1. Все n элементов должны быть случайными и равномерно разделенными.
  2. Общая сумма всех элементов должна быть равна s
  3. Ни один из элементов не может быть выше 1.0
  4. Код должен выполняться в течение 1 секунды для каждого n <= 10, независимо от s

Основываясь на этом ответе Stackoverflow, я знаю, как равномерно разделить элементы в заданном диапазоне. Например, с помощью n=5, s=4.5 я мог бы создать список из n-1 = 4 элементов в диапазоне [0, 1.5] с дополнительным начальным 0 и конечным 1.5. Затем я могу вычислить все различия (таким образом, общая сумма всех различий будет равна s=4.5). Вот возможная реализация этого:

int n=5; double s=4.5;

double[] randomValues = new double[n+1];
randomValues[n] = s;
for(int i=1; i<n; i++)
  randomValues[i] = Math.random()*s;
java.util.Arrays.sort(randomValues);
System.out.println("Random values:\n"+java.util.Arrays.toString(randomValues)+"\n");

double[] result = new double[n];
for(int i=0; i<n; i++)
  result[i] = Math.abs(randomValues[i]-randomValues[i+1]);
System.out.println("Result values:\n"+java.util.Arrays.toString(result)+"\n");

double resultSum = java.util.Arrays.stream(result).sum();
System.out.println("Sum: "+resultSum);
System.out.println("Is the result sum correct? "+(s==resultSum?"yes":"no"));

Пример вывода:

Random values:
[0.0, 1.3019797415889383, 1.9575834386978177, 2.0417721898726313, 4.109698885802333, 4.5]

Result values:
[1.3019797415889383, 0.6556036971088794, 0.08418875117481361, 2.0679266959297014, 0.39030111419766733]

Sum: 4.5
Is the result sum correct? yes

Try it online.

Это выше соответствует трем из четырех требований выше (1, 2 и 4). Однако не до 3.

Я мог бы зациклить его, пока один из элементов в массиве result все еще больше 1:

for(boolean flag=true; flag; ){
  ... // Same code as above

  flag=false;
  for(double d:result)
    if(d>1)
      flag=true;
}

This still works relatively fast for most n and s:
Try it online (отпечатки удаляются/перемещаются, чтобы не переполняться консоль)

Тем не менее, четыре //-отключенных тестовых случая в конце, со средними ожидаемыми случайными значениями, близкими к 1, занимают слишком много времени (и даже истекают через 60 секунд в TIO).

Так что это то, где мой вопрос в основном о. Как равномерно разделить значения, как это сделал я, И помнить о диапазоне [0, 1] для каждого значения, И иметь хорошую производительность? В связанном вызове кода-гольфа вверху я вижу несколько рабочих примеров. на других языках программирования, таких как Python или JavaScript, но перенос более длинных задач с кодовым гольфом с одного языка программирования на другой обычно не очень прост.


java random performance range uniform-distribution
person Kevin Cruijssen    schedule 18.05.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Хорошо, нашел решение на основе ответов JavaScript, которые уже были даны. Если s*s>n, я меняю s на n-s и устанавливаю флаг для использования 1-diff вместо diff в массиве результатов.

Итак, в сумме получается:

boolean inversedFlag = 2*s>n;
double S = s;
if(inversedFlag)
  S = n-S;

double[] result = new double[n];

for(boolean flag=true; flag; ){
  double[] randomValues = new double[n+1];
  randomValues[n] = S;
  for(int i=1; i<n; i++)
    randomValues[i] = Math.random()*S;
  java.util.Arrays.sort(randomValues);

  for(int i=0; i<n; i++){
    double diff = Math.abs(randomValues[i]-randomValues[i+1]);
    result[i] = inversedFlag ? 1-diff : diff;
  }

  flag=false;
  for(double d:result)
    flag |= d>1;
}

System.out.println("Result values:\n"+java.util.Arrays.toString(result)+"\n");

double resultSum = java.util.Arrays.stream(result).sum();
System.out.println("Sum: "+resultSum );
System.out.println("Is the result sum correct? "+(s==resultSum?"yes":"no"));

System.out.println();
System.out.println("--------------------------------------------------");
System.out.println();

Try it online.

Теперь мне просто нужно снова поиграть в гольф, но это не имеет отношения к этому вопросу о Stackoverflow. :)

person Kevin Cruijssen    schedule 19.05.2018