Randomly split a given number M into N parts

Question

So, the idea that I have, is to be able to divide $2.00 into 10 person, and each of them will receive $x.xx amount of money randomly. (N and M will always be limited to 2 decimals and > 0)

Ex: {0.12, 0.24, 1.03, 0.01, 0.2, 0.04, 0.11, 0.18, 0.05, 0.02}

Currently I have tried:

private static BigDecimal[] randSum(int n, double m)
{
    Random rand = new Random();
    BigDecimal randNums[] = new BigDecimal[n], sum = new BigDecimal(0).setScale(2);

    for (int i = 0; i < randNums.length; i++)
    {
        randNums[i] = new BigDecimal(rand.nextDouble()).setScale(2, RoundingMode.HALF_EVEN);
        sum = sum.add(randNums[i]);
    }

    for (int i = 0; i < randNums.length; i++)
    {
        BigDecimal temp1 = randNums[i].divide(sum, 2, RoundingMode.HALF_EVEN);
        BigDecimal temp2 = temp1.multiply(new BigDecimal(m).setScale(2));
        randNums[i] = temp2;
    }

    return randNums;
}

public static void main(String[] args)
{
    BigDecimal d[] = randSum(5, 2);

    double sum = 0;
    for (BigDecimal n : d)
    {
        sum += n.doubleValue();
        System.out.println(n);
    }
    System.out.println("total: " + sum);
}

But BigDecimals are too confusing and they don't add up. Sometimes the total is 1.98 or 2.01. Doubles doesn't work because of the Double-precision floating-point.

The code was taken from:

Getting N random numbers that the sum is M

I have fixed the conditions, N and M will always limited to 2 decimals and > 0 — feco, Aug 21 '15 at 08:39

Alex Salauyou · Accepted Answer · 2015-08-21T09:07:46.070

Let's suppose you need a fixed precision (passed as prec argument):

static public BigDecimal[] split(BigDecimal sum, int prec, int count) {
    int s = sum.scaleByPowerOfTen(prec).intValue();
    Random r = new Random();
    BigDecimal[] result = new BigDecimal[count];
    int[] v = new int[count];

    for (int i = 0; i < count - 1; i++)
       v[i] = r.nextInt(s);
    v[count - 1] = s;

    Arrays.sort(v);
    result[0] = BigDecimal.valueOf(v[0]).scaleByPowerOfTen(-prec);
    for (int i = 1; i < count; i++)
       result[i] = BigDecimal.valueOf(v[i] - v[i - 1]).scaleByPowerOfTen(-prec);
    return result;
}

This approach uses property that Random.nextInt() is uniformly distributed. After sorting, values of v[] array are points by which the whole amount is split, so you generate result using differences between neighboring elements:

[   2,    5,   10,   11, ...,  197,  200]  // v[]
[0.02, 0.03, 0.05, 0.01, ...,  ..., 0.03]  // result[]

Here you operate with integer values, so rounding issues don't bother anymore.

score 3 · Answer 2 · answered Aug 21 '15 at 08:53

I suggest to multiply all the numbers by 100 and rephrase your problem: generate the n random non-negative integer numbers which sum equals to the given m integer number. Later you can divide all the generated numbers by 100 to get what you want. Here's my implementation (similar to @SashaSalauyou version):

private static int[] randSum(int n, int min, int m) {
    Random rand = new Random();
    int[] nums = new int[n];
    int max = m - min*n;
    if(max <= 0)
        throw new IllegalArgumentException();
    for(int i=1; i<nums.length; i++) {
        nums[i] = rand.nextInt(max);
    }
    Arrays.sort(nums, 1, nums.length);
    for(int i=1; i<nums.length; i++) {
        nums[i-1] = nums[i]-nums[i-1]+min;
    }
    nums[nums.length-1] = max-nums[nums.length-1]+min;
    return nums;
}

I also added one more parameter, min which is the minimal wanted number. Set it to 0 if you accept zeros in the answer. Otherwise you may set it to 1 (then after division by 100 the lowest possible number will be 0.01).

Thanks, this is also an excellent solution, by using just integers, it will have better performance. But I will give the credit to @SashaSalauyou, because he gave the first answer. I wish I could accept both.. — feco, Aug 21 '15 at 09:10

amit · Answer 3 · 2015-08-21T09:03:38.930

You can treat this problem as integers, and instead of summing to M, make it sum to 100M.

Do the algorithm, and you will end up with non-integers number, such as 10.345,
Now - basically what you would like to do is take the floor value of each number (10 in the above example), and to increase the number to 11 with probability proportional to 0.345.

That can be done by creating the reminder array: rem[i] = value[i] - ceil(value[i]), and choose M - sum{ceil(value[i])} values with replacements, according to the weighted probability of rem array.

Code:

public static BigDecimal[] createRandomSumsTo(BigDecimal M, int n) { 
    int m = M.multiply(BigDecimal.TEN).multiply(BigDecimal.TEN).intValue();
    double[] rands = new double[n];
    double sum = 0;
    for (int i = 0; i < n; i++) {
        rands[i] = rand.nextDouble();
        sum += rands[i];
    }
    for (int i = 0; i < n; i++) rands[i] = (rands[i] / sum) * m;
    int[] intVals = new int[n];
    double[] rem = new double[n];
    //create base and reminder array:
    for (int i =0 ; i < n; i++) { 
        intVals[i] = (int) Math.floor(rands[i]);
        rem[i] = rands[i] - intVals[i];
    }
    //for efficiently chosing a random value by weight
    double[] aux = new double[n+1];
    for (int i = 1 ; i < n+1; i++) { 
        aux[i] = aux[i-1] + rem[i-1]; 
    }
    //normalize to sum to one.
    for (int i = 0 ; i < n+1; i++) { 
        aux[i] = aux[i] / aux[n]; 
    }
    int intsSum = 0;
    for (int x : intVals) {
        intsSum += x;
    }
    for (; intsSum < m; intsSum++) { 
        intVals[chooseWeighted(aux)]++;
    }
    //and create the BigDecimal array:
    BigDecimal[] res = new BigDecimal[n];
    for (int i = 0; i < n; i++) { 
        res[i] = new BigDecimal(intVals[i]).divide(BigDecimal.TEN).divide(BigDecimal.TEN);
    }

    return res;

}

private static int chooseWeighted(double[] probabilities) {
    double r = rand.nextDouble();
    int idx = Arrays.binarySearch(probabilities, r);
    if (idx >= 0) return idx-1;
    return (-1*idx) -2;
}

Randomly split a given number M into N parts

3 Answers3