将 `n` double 均匀除以总和 `s`，其中每个 double 都小于 1（具有适当的性能）

Question

我目前正在研究 this (code-golf) challenge，我很难将给定整数 n 和小数总和 s 的四个要求结合起来]（考虑到我们应该支持的范围：1 <= n <= 10 和 0 <= s <= n）：

n项全部随机，均匀分配
所有项目的总和必须等于s
None 的项目可能高于 1.0
代码必须运行每 n <= 10 1 秒内，无论 s

基于this Whosebug answer我知道如何在给定范围内统一划分项目。例如，使用 n=5, s=4.5，我可以在 [0, 1.5] 范围内创建一个包含 n-1 = 4 项目的列表，并在前导 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-array 中的一个项目仍然大于 1:

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

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

对于大多数 n 和 s:
这仍然相对较快 Try it online（打印 removed/moved 不会溢出控制台）

然而，最后的四个 //-禁用测试用例，预期随机值的平均值接近 1，花费的时间太长（甚至在 60 秒后超时） TIO).

所以这就是我的主要问题所在。 如何像我一样统一划分值，并牢记每个值的 [0, 1] 范围，并获得良好的性能？ 在链接的代码高尔夫挑战中我在其他编程语言中看到了一些工作示例，例如 Python 或 JavaScript，但是将较长的代码高尔夫挑战从一种编程语言移植到另一种编程语言通常不是很简单..

Answer 1

好的，根据已给出的 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.

现在我只需要再次打高尔夫球，但这与这个 Whosebug 问题无关。 :)

将 `n` double 均匀除以总和 `s`，其中每个 double 都小于 1（具有适当的性能）

Uniformly divide `n` doubles with a total sum `s`, where each double is below 1 (with proper performance)

java

random

performance

range

uniform-distribution