如果给你一个问题：“随机产生和为S的N个正整数”， 你会如何做呢？
针对该问题，解决的方法有很多种。在这篇文章中，我将为大家给出两种比较好理解的解决方法：一个是“尺子法”；另外一个是“锯木头法”。 (名字随便取的，主要是方便理解用)。
方法一：尺子法
思想：
将给定值S看成一个尺子的长度，那么，生成N个和为S的正整数的问题就变成在尺子中寻找出N-1个不同的刻度，加上最小刻度0和最大刻度S， 一共有N+1个刻度。然后，从小到大，计算出相邻刻度的长度，这些长度就可以认为是随机的，因为尺子中产生的N-1个刻度是随机的。
有了上述思想，我们只要如下三个步骤就能完成这个功能。
- 验证参数S和N的正确性
- 尺子中产生N-1个不同刻度
- 计算相邻刻度之间的值
/*** ** 随机产生和为sum(如10)的num(如5)个正整数 *
* * @param num * 期望产生的随机数个数 * @param sum * 所有产生随机数的和 * @return 返回满足和为sum的num个随机正整数组成的数组 */ public Integer[] random(int num, int sum) { /** * Step1: 验证参数正确性 */ if (num < 1) { throw new IllegalArgumentException("产生随机数个数的num不能小于1"); } if (sum < num) { throw new IllegalArgumentException("产生随机数个数的num不能大于和sum"); } if (sum <= 0) { throw new IllegalArgumentException("sum需要为正整数"); } /** * Step2: 0~sum之间随机产生num-1个不同的刻度 */ Random rand = new Random(); Setlocations = new TreeSet<>(); while (locations.size() < num - 1) { locations.add(rand.nextInt(sum - 1) + 1); } locations.add(0); locations.add(sum); /** * Step3: 计算出相邻刻度的差，计算出来的长度就可以代表一个随机数 */ Integer[] locationsArray = locations.toArray(new Integer[] {}); Integer[] resultArray = new Integer[num]; for (int i = 0; i < num; i++) { resultArray[i] = locationsArray[i + 1] - locationsArray[i]; } return resultArray; }
方法二：锯木头法
思想：
锯木头法的思想则是将S看成木头的长度，随机产生和为S的N个正整数的问题转换成锯N-1次木头，将产生N段小木头，N段的小木头其长度和就是S。
有了上述思想，我们便可以通过如下几个步骤实现该方法：
- 验证参数S和N的正确性
- 锯N-1次木头
在锯木头的时候，需要考虑可锯的长度。
/*** ** 随机产生和为sum(如10)的num(如5)个正整数 *
* * @param num * 期望产生的随机数个数 * @param sum * 所有产生随机数的和 * @return 返回满足和为sum的num个随机正整数组成的数组 */ public int[] random2(int num, int sum) { /** * Step1: 验证参数正确性 */ if (num < 1) { throw new IllegalArgumentException("产生随机数个数的num不能小于1"); } if (sum < num) { throw new IllegalArgumentException("产生随机数个数的num不能大于和sum"); } if (sum <= 0) { throw new IllegalArgumentException("sum需要为正整数"); } /** * 如果只有一个 直接返回 */ if (num == 1) { return new int[] { sum }; } /** * Step2: 锯木头的方法 */ Random rand = new Random(); int[] randomNumbers = new int[num]; // 剩余数 int remainingNum = sum; for (int i = 0; i < num - 1; i++) { /** * 可以锯掉可选值 * remaining - (num - (i+1)) + 1 = remainingNum - num + i + 1 */ int randNum = rand.nextInt(remainingNum - num + i + 1) + 1; remainingNum -= randNum; randomNumbers[i] = randNum; } /** * 最后一个直接赋值即可 */ randomNumbers[num - 1] = remainingNum; return randomNumbers; }
详细代码及某次测试运行结果如下：
import java.util.Random;import java.util.Set;import java.util.TreeSet;/** * @author wangmengjun * */public class RandomExample_1 { /*** * * 随机产生和为sum(如10)的num(如5)个正整数 *
* * @param num * 期望产生的随机数个数 * @param sum * 所有产生随机数的和 * @return 返回满足和为sum的num个随机正整数组成的数组 */ public Integer[] random(int num, int sum) { /** * Step1: 验证参数正确性 */ if (num < 1) { throw new IllegalArgumentException("产生随机数个数的num不能小于1"); } if (sum < num) { throw new IllegalArgumentException("产生随机数个数的num不能大于和sum"); } if (sum <= 0) { throw new IllegalArgumentException("sum需要为正整数"); } /** * Step2: 0~sum之间随机产生num-1个不同的刻度 */ Random rand = new Random(); Set locations = new TreeSet<>(); while (locations.size() < num - 1) { locations.add(rand.nextInt(sum - 1) + 1); } locations.add(0); locations.add(sum); /** * Step3: 计算出相邻刻度的差，计算出来的长度就可以代表一个随机数 */ Integer[] locationsArray = locations.toArray(new Integer[] {}); Integer[] resultArray = new Integer[num]; for (int i = 0; i < num; i++) { resultArray[i] = locationsArray[i + 1] - locationsArray[i]; } return resultArray; } /*** * * 随机产生和为sum(如10)的num(如5)个正整数 *
* * @param num * 期望产生的随机数个数 * @param sum * 所有产生随机数的和 * @return 返回满足和为sum的num个随机正整数组成的数组 */ public int[] random2(int num, int sum) { /** * Step1: 验证参数正确性 */ if (num < 1) { throw new IllegalArgumentException("产生随机数个数的num不能小于1"); } if (sum < num) { throw new IllegalArgumentException("产生随机数个数的num不能大于和sum"); } if (sum <= 0) { throw new IllegalArgumentException("sum需要为正整数"); } /** * 如果只有一个 直接返回 */ if (num == 1) { return new int[] { sum }; } /** * Step2: 锯木头的方法 */ Random rand = new Random(); int[] randomNumbers = new int[num]; // 剩余数 int remainingNum = sum; for (int i = 0; i < num - 1; i++) { /** * 可以锯掉可选值 * remaining - (num - (i+1)) + 1 = remainingNum - num + i + 1 */ int randNum = rand.nextInt(remainingNum - num + i + 1) + 1; remainingNum -= randNum; randomNumbers[i] = randNum; } /** * 最后一个直接赋值即可 */ randomNumbers[num - 1] = remainingNum; return randomNumbers; }}
import java.util.Arrays;/** * @author wangmengjun * */public class Main { public static void main(String[] args) { RandomExample_1 example1 = new RandomExample_1(); int num = 6; int sum = 30; System.out.println(String.format("随机产生和为%d的%d个正整数", sum, num)); for (int i = 1; i <= 10; i++) { System.out.println(String.format("第%d遍random()产生结果 -- %s", i, Arrays.toString(example1.random(num, sum)))); System.out.println(String.format("第%d遍random2()产生结果 -- %s", i, Arrays.toString(example1.random2(num, sum)))); } }}
随机产生和为30的6个正整数
第1遍random()产生结果 -- [2, 4, 4, 6, 5, 9]
第1遍random2()产生结果 -- [24, 1, 2, 1, 1, 1]
第2遍random()产生结果 -- [6, 4, 1, 1, 6, 12]
第2遍random2()产生结果 -- [17, 1, 5, 5, 1, 1]
第3遍random()产生结果 -- [1, 15, 1, 6, 3, 4]
第3遍random2()产生结果 -- [2, 4, 1, 7, 9, 7]
第4遍random()产生结果 -- [16, 1, 1, 4, 5, 3]
第4遍random2()产生结果 -- [11, 4, 6, 5, 1, 3]
第5遍random()产生结果 -- [4, 4, 6, 7, 4, 5]
第5遍random2()产生结果 -- [6, 13, 1, 3, 6, 1]
第6遍random()产生结果 -- [10, 1, 16, 1, 1, 1]
第6遍random2()产生结果 -- [18, 7, 2, 1, 1, 1]
第7遍random()产生结果 -- [4, 1, 10, 8, 2, 5]
第7遍random2()产生结果 -- [8, 6, 6, 4, 3, 3]
第8遍random()产生结果 -- [1, 6, 3, 8, 1, 11]
第8遍random2()产生结果 -- [4, 7, 3, 7, 2, 7]
第9遍random()产生结果 -- [3, 5, 13, 3, 1, 5]
第9遍random2()产生结果 -- [13, 4, 1, 4, 2, 6]
第10遍random()产生结果 -- [4, 5, 12, 3, 3, 3]
第10遍random2()产生结果 -- [17, 3, 7, 1, 1, 1]