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

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

0 голосов
/ 18 мая 2018

В настоящее время я работаю над этой задачей (code-golf) , и мне тяжело комбинировать четыре требования, учитывая целое число 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

Попробуйте онлайн.

Это выше соответствует трем из четырех требований выше (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;
}

Это все еще работает относительно быстро для большинства n и s:
Попробуйте онлайн (отпечатки удаляются / перемещаются, чтобы не переполнять консоль)

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

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

1 Ответ

0 голосов
/ 19 мая 2018

Хорошо, найдено решение, основанное на ответах 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();

Попробуйте онлайн.

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

...