如何生成一个n个随机正整数序列，它们加起来有些值？
我正在尝试生成一个整数数组，其中包含与特定值相加的randoms。 这是我的代码：
private long[] getRandoms(long size , long sum) throws Exception { double iniSum = 0; System.out.println("sum = " + sum); long[] ret = new long[(int) size]; for (int i = 0 ; i < ret.length; i++) { ret[i] = randomInRange(1, sum); iniSum += ret[i]; } double finSum = 0; for (int i = 0 ; i < ret.length; i++) { ret[i] = Math.round((sum * ret[i]) / iniSum); System.out.println("ret[" + i +"] = " + ret[i]); finSum += ret[i]; } if (finSum != sum) throw new Exception("Could not find " + size + " numbers adding up to " + sum + " . Final sum = " + finSum); return ret; } private long randomInRange(long min , long max) { Random rand = new Random(); long ret = rand.nextInt((int) (max - min + 1)) + min; System.out.println("ret = " + ret); return ret; } 但是，结果并不准确，例如：
找不到100个数字，总计4194304。 最终总和= 4194305.0
我想我在这方面失去了准确性：
(sum * ret[i]) / iniSum
您能否在我的代码中推荐替代算法或修复程序，以帮助我实现此目标？
每次使用ret[i] = Math.round((sum * ret[i]) / iniSum)缩放值时，您将失去一些精度，部分来自除法运算本身，但主要是通过将缩放值存储为整数。 后一种情况类似于比例选举制度，其中少数席位必须分配给更多的选票。
减轻这种情况的两种方法：
首先缩放列表中的所有值，但要跟踪理想缩放值（实数）和存储的缩放值之间的差异。 使用截断而不是舍入，使得差异始终是正的。 如果存在差异，则可以按理想量和当前存储量之间的差值的顺序递增某些值。
long finSum = 0; // Might as well be a long float[] idealValues = new float[size]; for (int i = 0 ; i < ret.length; i++) { ideal[i] = (sum * ret[i]) / iniSum; ret[i] = (long) (ideal[i]); // Truncate, not round System.out.println("ret[" + i +"] = " + ret[i]); finSum += ret[i]; } /* There are iniSum - finSum extra amounts to add. */ for (int i = 0; i < iniSum - finSum; i++) { /* Pick a target slot to increment. This could be done by keeping a priority queue. */ int target = 0; float bestScore = 0.0; for (int j = 0; j < size; j++) { float score = (ideal[j] - ret[j])/ret[j]; if (score > bestScore) { target = j; bestScore = score; } } /* Allocate an additional value to the target. */ ret[target]++; }
或者更简单地说，您可以将列表中的最后一个值设置为缩放后执行所有其他值。 然而，这在统计上会扭曲输出。
刚才有个主意。 将数组初始化为全0。随机选择数组中的数字并增加1并将总和减1，直到sum为0.当sum很大时，它根本不实用:)
long ret = new long[size]; for(int i=0;i
是的，有一种标准方法可以避免浮点不准确。 它与计算n个数加到s的方式数的方法有关 。 它并不复杂，但奇怪的是还没有人提到它，所以这里是：
想象一下，我们有一个字符串，其中包含n-1 X和s 。 因此，例如，对于s = 5，n = 3，将是一个示例字符串
oXooXoo
请注意，X将o分为三个不同的分组：长度为1，长度为2，长度为2.这对应于解[1,2,2]。 每个可能的字符串为我们提供了一个不同的解决方案，通过计算组合在一起的o的数量（0是可能的：例如， XoooooX将对应于[0,5,0]） 。
因此，我们需要做的就是想象通过为n-1 X选择随机位置来创建这样的字符串，然后找出对应的解决方案。 这是一个更详细的细分：
- 在
[1, s+n-1]之间生成n-1唯一随机数 。 使用拒绝采样这样做很简单 – 如果选择一个数字两次，只需删除它并选择另一个。 - 对它们进行排序，然后计算出每个X之间的o数 。 这个数字结果是
currentValue - previousValue - 1。
最后，这里有一些示例Java（未经测试）应该这样做：
private List getRandomSequenceWithSum(int numValues, long sum) { List xPositions = new List (); List solution = new List (); Random rng = new Random(); //Determine the positions for all the x's while(xPositions.size() < numValues-1) { //See https://stackoverflow.com/a/2546186/238419 //for definition of nextLong long nextPosition = nextLong(rng, sum+numValues-1) + 1; //Generates number from [1,sum+numValues-1] if(!xPositions.contains(nextPosition)) xPositions.add(nextPosition); } //Add an X at the beginning and the end of the string, to make counting the o's simpler. xPositions.add(0); xPositions.add(sum+numValues); Collections.sort(xPositions); //Calculate the positions of all the o's for(int i = 1; i < xPositions.size(); i++) { long oPosition = xPositions[i] - xPositions[i-1] - 1; solution.add(oPosition); } return solution; }
我相信您的问题在于Math.round尝试修改您的代码以使用双精度并避免任何精度损失
一个好方法是使用一个间隔列表，然后在每个步骤中拆分。 这是伪代码
array intervals = [(0,M)] while number intervals
如果你想要非常小心，你需要检查你的分裂点x不是间隔的终点。 您可以通过拒绝来执行此操作，或者您可以选择要拆分的间隔，然后选择拆分该间隔的位置，但在这种情况下，您需要注意不要引入偏差。 （如果你关心偏见）。
这个怎么样：
long finSum = 0; for (int i = 0 ; i < ret.length; i++) { ret[i] = Math.round((sum * ret[i]) / iniSum); System.out.println("ret[" + i +"] = " + ret[i]); finSum += ret[i]; } ret[0] += sum - finSum;
换句话说，将所有舍入误差放入第一个元素中。
建议：
for (int i = 0 ; i < ret.length; i++) { ret[i] = randomInRange(1, sum); iniSum += ret[i]; }
在第一个for循环中，不使用从0到（ret.length-1）的迭代，而是仅使用从0到（ret.length-2）的迭代。 保留最后一个元素进行调整。
也不要调用randomInRange（1，sum），而是使用randomInRange（1，sum-iniSum）。 这将减少所需的标准化。
最后，最后一个输出数将是（sum-iniSum）。 因此，可以去除第二个for循环。
拿个号码。 从中减去一个合理的随机数。 重复，直到你有足够的数字。 根据定义，它们的总和是固定的并且等于初始数。 你正好进行n操作，其中n是你需要的数量; 没有猜测。
这是Python代码：
import random def generate_randoms(initial, n): # generates n random numbers that add up to initial. result = [] # empty list remainder = initial # we'll subtract random numbers and track the remainder numbers_left = n while numbers_left > 1: # guarantee that each following step can subtract at least 1 upper_bound = remainder - numbers_left next_number = random.randrange(1, upper_bound) # [1, upper_bound) result.append(next_number) remainder -= next_number # chop off numbers_left -= 1 result.append(remainder) # we've cut n-1 numbers; don't forget what remains return result
它有效，但它有一个缺点：数字越远，它们就越小。 您可能需要对结果列表进行随机播放以对抗此操作，或者使用较小的上限进行播放。
这肯定是一个有趣的问题（upvote！），我期待看到一些更有创意的解决方案。 我在你列出的代码中遇到的一个问题是你使用的是Random类，它只返回整数而不是long，但是你只需要将它转换为long。 因此，如果您的函数真的需要多头，那么您将不得不找到一个不同的随机数生成器。
“理想”解决方案是生成所有可能的添加剂组合（称为分区），然后随机选择一个。 然而，最有名的算法确实非常昂贵。 关于这个问题有很多好的源材料。 这是一个关于分区算法的特别好的读物：
http://www.site.uottawa.ca/~ivan/F49-int-part.pdf
部分问题是在这个例子中找出“随机”的含义。 例如，如果您要查找总数为1000的5个数字的数组，{1000,0,0,0,0}与{200,200,200,200,200}一样有效，这与{136,238,124,66,436}一样有效。 。 具有产生任何这些集合的相等机会的算法将是真正随机的。
但是，我猜你不是在寻找一个完全随机的分布，而是介于两者之间。
不幸的是，我的Java非常生疏，而且我现在用C＃做大部分事情，所以我将介绍C＃…它不应该花费太多的翻译来将这些算法转换成Java。
以下是我对这个问题的看法：
public int[] GetRandoms( int size, int sum, Random r=null ) { if( r==null ) r = new Random(); var ret = new int[size]; while( sum > 0 ) { var n = r.Next( 1, (int)Math.Ceiling((double)sum/size)+1 ); ret[r.Next(size)] += n; sum -= n; } return ret; }
（实际上，看看我是如何在我的随机数生成器中传递的？我将其默认为null并且为了方便起见只创建一个新的，但现在我可以传入一个种子随机数生成器，并生成相同的结果如果我愿意，这对于测试目的很有用。每当你有一个利用随机数发生器的方法时，我强烈建议采用这种方法。）
该算法基本上不断地将随机数添加到arrays中的随机条目，直到达到总和。 由于它的附加性质，它将有利于更大的数字（即，结果中出现小数字的可能性极小）。 但是，这些数字似乎是随机的，它们会相应地相加。
如果你的目标数量很小（100以下），你实际上可以实现生成所有分区的真正随机方法，只需随机选择一个。 例如，这是一个分区算法（礼貌http://homepages.ed.ac.uk/jkellehe/partitions.php ，翻译成C＃）：
public List GetPartitions( int n ) { var result = new List(); var a = new int[n+1]; var k = 1; a[0] = 0; var y = n - 1; while( k != 0 ) { var x = a[k-1] + 1; k--; while( 2*x <= y ) { a[k] = x; y -= x; k++; } var l = k + 1; while( x <= y ) { a[k] = x; a[l] = y; result.Add( a.Take( k + 2 ).ToArray() ); x++; y--; } a[k] = x + y; y = x + y - 1; result.Add( a.Take( k + 1 ).ToArray() ); } return result; }
（为了帮助你进行Java翻译， a.Take(x)意味着从数组中取出第一个x元素...我确信这些天来Java中存在一些等效的魔法。）
这将返回一个分区列表...只需随机选择一个，您将获得完美的随机分布。
-这个怎么样？
private long[] getRandoms(int size , long sum) { long[] array = new long[size]; long singleCell = sum / size; Arrays.fill(array, singleCell); array[size-1] += sum % singleCell; int numberOfCicles = randomInRange(size, size*10); for (int i = 0; i < numberOfCicles; i++) { int randomIndex = randomInRange(0, size); long randomNumToChange = randomInRange(0, array[randomIndex]); array[randomIndex] -= randomNumToChange; array[randomInRange(0, size)] += randomNumToChange; } return array; }