vendredi 18 mai 2018

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

I'm currently working on this (code-golf) challenge, and I'm having a hard time of combining the four requirements given an integer-amount n, and total decimal-sum s (given the ranges we're supposed to support: 1 <= n <= 10 and 0 <= s <= n):

  1. The n items should all be random, and uniformly divided
  2. The total sum of all items must be equal to s
  3. None of the items may be above 1.0
  4. The code must run within 1 second for every n <= 10, regardless of s

Based on this Stackoverflow answer I know how to uniformly divide items in a given range. For example, with n=5, s=4.5, I could create a list of n-1 = 4 items in the range [0, 1.5], with an additional leading 0 and trailing 1.5. Then I can calculate all the differences (so the total sum of all differences will be equal to s=4.5). Here a possible implementation of that:

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"));

Example output:

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.

This above complies to three of the four requirements above (1, 2, and 4). However, not to 3.


I could wrap a loop around it, which continues as long as one of the items in the result-array is still larger than 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 (prints are removed/moved to not overflow the console)

However, the four //-disabled test cases at the end, with averages of the expected random values nearing the 1, take way too long (and even time out after 60 seconds on TIO).

So this is where my question is mostly about. How to uniformly divide the values like I did, AND keep in mind the range of [0, 1] for each values, AND have a good performance? In the linked code-golf challenge at the top I see some working examples in other programming languages, like Python or JavaScript, but porting longer code-golfed challenges from one programming languages to another usually isn't very straight-forward..




Aucun commentaire:

Enregistrer un commentaire