在多个指定区间内生成随机数，且随机数总和固定算法

2022-12-05 18:57:10

在多个指定区间内生成随机数，且随机数总和固定算法

一、介绍

最近项目上遇到了一个需求就是在多个指定区间内生成总和恒定的随机数。
示例：在[1-3]、[4-20]、[24-100]区间上分别生成一个随机数且要求随机数总和为40。
输出：随机数 a = 2 、b = 5 、c = 33.
想了一整天，最后用一种不是太完美的方法解决了这个问题。

二、思路简述

在多个指定区间生成随机数这个好弄，但是要求总和恒定就有点难办了。
下边的思路我会用用上面的示例来解释。

首先我们可以确定的是这个随机数的总和肯定是要>=1+4+24、<= 3+20+100的。即 >=所有区间最小值的和，<=所有区间最大值的和。
如果我们生成了一个随机数，我们用总值 - 生成的数 = 剩下的总值那么剩下的总值也必然满足 >=剩下区间的最小值总和，<=剩下区间最大值总和。
例如如我们生成 a=2 ，那么剩下总和为38，那么判断 38 是否满足 >=27 && <=123，如果满足则这个数符合规矩，我们只要在每次生成随机数后进行判断是否满足这个条件就可以了，如果不满足就继续生成。
如果前面的随机数都满足条件，那么最后一个数也必然满足条件。我们不用判断最后一个数，直接用最后剩下的总和即可。

问题

用我上面的思路去做必然会生成一组符合条件的随机数，但会出现一个问题。经过大量数据测试你会发现，我们设定的总和离边界值越近，生成的时间越长。这是为什么呢？

这是因为在我们的算法中，随机数每次都是在我们规定的区间内生成数据，前边生成的数据会对后边的值产生一定影响。如果前面生成的数过大，可能后边的数就要适当小一些才能满足要求。

当我们设定的总和离边界值远时，这时随机数可取的范围比较大，比如说此时我们设定随机数的总和为75，也就是随机数可取值的中位数。此时离边界是最远的，那么无论前边取何值，对后边的影响都会较小。一组随机数更可能达到要求。

但如果设定值正好为27或123那么此时随机数的取值已经是固定的。我们可以简单计算下如果我们设置边界值为27那么随机数总和为27的概率就为 1/3 * 1/16 * 1/76

这还是只取三个随机数，如果我们要求的是10个、100个呢。那概率可就够小了。

解决方案
我的改进办法就是在每次判断后将随机数生成的范围缩小。

例如我第一次生成了5，第二次生成了20，我发现剩余总值为15，此时我们明白我们生成的数过大了，我们可以为15为第二个随机数的最高值来生成随机数，即可。即第二次在4-15上生成。这样的就会大大减少随机数生成的次数，从而减少算法消耗时间。

3. 代码展示

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * @author lixiangxiang
 * @description 随机数算法
 * @date 2021/7/14 14:10
 */
public class RandomAlgorithm {

    public static void main(String[] args) {
        List<PveScoreRule> rules = new ArrayList<>();
        int minTotal = 0;
        int maxTotal = 0;
        int total = 0;

        //生成分数范围
        for (int i = 0; i < 10; i++) {
            //生成最大边界
            int max = new Random().nextInt(109) % (109+1);
            //生成最小边界
            int min = new Random().nextInt(109) % (109+1);
            //如果min>max交换两者顺序
            if (max < min) {
                int temp = min;
                min = max;
                max = temp;
            }
            //得出随机数总和最高范围
            maxTotal += max;
            //得出随机数总和最低范围
            minTotal += min;
            rules.add(new PveScoreRule(max,min));
        }
        total = new Random().nextInt(maxTotal) % (maxTotal - minTotal + 1) + minTotal;

        //打印并验证随机数是否合法
        int num = 10;
        List<PveScoreRule> errRule = new ArrayList<>();
        int[] errArr = new int[10];

		//验证数据是否合法
        for (int i = 0; i < 10000; i++) {
            boolean flag = true;
            int sum = 0;
            int[] scores = createPveScore(rules,minTotal,maxTotal,total);

            for (int j = 0; j < scores.length; j++) {
                if (rules.get(j).max < scores[j]||rules.get(j).min>scores[j]) {
                    flag = false;
                    errRule = rules;
                    errArr = scores;
                }
                System.out.print(scores[j]+"-");
                sum += scores[j];
            }
        }
        System.out.println("-"+flag)
        System.out.println("======"+Arrays.toString(errRule.toArray()));

    }

    /**
     * description: 创建随机分数
     *
     * @author: lixiangxiang
     * @param rules 每个分数的范围
     * @param minTotal 总分最小下限
     * @param maxTotal 总分最大上限
     * @param total 总分
     * @return int[]
     * @date 2021/7/14 22:18
     */
    public static int[] createPveScore(List<PveScoreRule> rules,int minTotal,int maxTotal,int total) {
        //存放随机数的数组
        int[] randoms = new int[rules.size()];
        for (int i = 0; i < rules.size(); i++) {
            //生成随机数 范围最小值到范围最大值
            int max = rules.get(i).max;
            int min = rules.get(i).min;
            //生成到最后一个时，直接将剩余的总数赋给他
            if(i == rules.size()-1){
                randoms[i] = total;
                if(total > max || total < min) {
                    System.out.println(rules);
                    System.out.println(Arrays.toString(randoms));
                }
                return randoms;
            }

            int score = new Random().nextInt(max) % (max - min + 1) + min;
            //计算剩余的总数、最大边界和最小边界
            minTotal -= rules.get(i).min;
            maxTotal -= rules.get(i).max;
            int remandTotal = total - score;
            //判断生成的数是否有问题
            //1. 判断其剩余总数是否大于最大值 总数是否小于最小值如果有一个满足则进行循环,直到随机数可行时
            while(remandTotal > maxTotal || remandTotal < minTotal) {
                if (remandTotal > maxTotal) {
                    //如果比之大说明随机数需要取更大值
                    //通过改变随机数生成的下限，让其下限等于当前的随机数
                    min = score;
                }
                //1. 判断其剩余总数是否小于最小值
                else {
                    //如果比之大说明随机数需要取更小值
                    //通过改变随机数生成的下限，让其上限等于当前的随机数
                    max = score;
                }
                //重新生成随机分数
                score = new Random().nextInt(max) % (max - min + 1) + min;
                //重新计算剩余的总数
                remandTotal = total - score;
            }
            //如果上述条件都不成立，说明随机数合法存入到数组中
            randoms[i] = score;
            //计算真正剩余总值
            total -= score;
        }
        return randoms;
    }
}


class PveScoreRule {
    int max;
    int min;

    public PveScoreRule(int max, int min) {
        this.max = max;
        this.min = min;
    }


    @Override
    public String toString() {
        return "PveScoreRule{" +
                ", max=" + max +
                ", min=" + min +
                '}';
    }
}

码农公寓