将给定的数字M随机分成N份

Question

所以，我的想法是将$2.00分给10个人，每个人随机收到$x.xx的金额。(N和M始终限制为2个小数点且>0)

例如：{0.12, 0.24, 1.03, 0.01, 0.2, 0.04, 0.11, 0.18, 0.05, 0.02}

目前我尝试过:

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

但是BigDecimal太复杂了，而且它们的总和有时是1.98或2.01。双精度浮点数不适用于Double-precision floating-point。

代码来自:

获取N个随机数使其总和为M

- feco

---

如果 m == 1.234 怎么办？你永远无法生成这样的数值。 - Tagir Valeev

我已经修正了条件，N和M将始终限制在2个小数位且大于0。 - feco

Answer 1

假设您需要固定精度（作为prec参数传递）：

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;
}

这种方法利用了Random.nextInt()均匀分布的属性。排序后，v[]数组的值是整个金额被拆分的点，因此您可以使用相邻元素之间的差异来生成结果：

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

在这里，您使用整数值，因此不再需要担心舍入问题。

- Alex Salauyou

Answer 2

我建议将所有数字乘以100并重新表述您的问题：生成n个随机非负整数，它们的和等于给定的整数m。稍后，您可以将生成的所有数字除以100以获得所需结果。这是我的实现（类似于@SashaSalauyou版本）：

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;
}

我还添加了一个参数min，表示所需的最小数字。如果您接受答案中包含零，请将其设置为0。否则，您可以将其设置为1（然后在除以100后，最低可能的数字将是0.01）。

- Tagir Valeev

---

谢谢，这也是一个很好的解决方案，通过只使用整数，它将具有更好的性能。但我会把功劳归给@SashaSalauyou，因为他给出了第一个答案。我希望我能接受两个答案.. - feco

Answer 3

您可以将此问题视为整数，而不是求和到M，而是使其求和到100M。

进行算法，您将得到非整数数字，例如10.345，
现在 - 基本上您想要做的是取每个数字的底数（以上面的示例中的10为例），并使用与0.345成比例的概率将数字增加到11。

这可以通过创建余数数组来完成：rem[i] = value[i] - ceil(value[i])，并根据rem数组的加权概率选择替换的值中的M - sum{ceil(value[i])}个数。

代码：

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;
}

- amit