如何生成一系列加起来等于某个值的n个随机正整数？

Question

我正在尝试生成一个包含随机整数的数组，使它们相加等于特定的值。这是我的代码：

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

你能否推荐一种替代算法或修复我的代码，以帮助我实现这个目标？

- Dhruv

---

我尝试生成一个包含随机整数的数组，这些整数加起来得到特定的值。这是否意味着集合中至少有一个值是不随机的？ - Andrew Thompson

@AndrewThompson 很有趣！ - assylias

@AdamMihalcin 每次异常都不同，因为在辅助方法中调用了 Math.random。 - Dhruv

说句题外话，单元测试不应该有随机行为。它们应该具有特定设计行为，以测试特定情况。 - Reverend Gonzo

@QuantumMechanic：取n个随机数（在任何范围内，只要分布均匀），将它们相加，然后将它们全部除以总和是生成n个随机“公平”数字的标准方法，这些数字从[0,1]中选择，其总和为1。显然，将它们乘以另一个数字k将给您n个随机“公平”数字，这些数字来自[0,k]。 - BlueRaja - Danny Pflughoeft

Answer 1

每次使用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]++;
}

或者更简单地，您可以将列表中的最后一个值设置为在缩放所有其他值后仍然未解决的值。然而，这会在统计上偏移输出结果。

- Edmund

---

我喜欢这种方法，但是你可以通过选择一个随机的插槽来释放那些额外的数量。我认为它不会比现有的方法更加偏向分布。 - Michael Anderson

这个解决方案可以缓解浮点数不精确的问题，但并不能完全消除它。还有一些不依赖于浮点数的解决方案，比如@woodings或者我的回答。 - BlueRaja - Danny Pflughoeft

Answer 2

我有一个想法。将数组初始化为0。在数组中随机选择一个数字，并将其增加1，同时将总和减1，直到总和为0。当总和很大时，这种方法实际上并不可行 :)

long ret = new long[size];
for(int i=0;i<size;i++) ret[i]=0;
for(int i=0;i<sum;i++) {
  int n = random(0,size);
  ret[n]++;
}

- woodings

---

这种方法的优点是不带偏见，但缺点是速度较慢。 - Michael Anderson

一种修改方法是将数字平均（或近似平均）分成N份，然后重复随机选择两个部分并在它们之间移动一些值。有点像洗牌。我不确定需要多少次洗牌才能得到真正的随机结果。您还可以逐渐减少这种移动量，从大到小开始，这可能会给出更好的数字分布。 - Michael Anderson

Answer 3

是的，有一种标准方法可以避免浮点不精确性。它与计算n个数字总和为s的方式数量的方法有关。这并不复杂，但奇怪的是还没有人提到过它，所以我来介绍一下：

---

假设我们有一个包含n-1个X和s个o的字符串。例如，当s=5，n=3时，一个示例字符串可能是“oXooXoo”。注意，X将o分成三个不同的组：长度为1、长度为2和长度为2。这对应于解[1,2,2]。每个可能的字符串都会给我们一个不同的解，通过计算分组在一起的o的数量（0也是可能的：例如，“XoooooX”对应于[0,5,0]）。因此，我们所需要做的就是想象创建这样一个字符串，通过选择n-1个X的随机位置，然后弄清楚它对应的解是什么。下面是更详细的说明：

生成n-1个介于[1, s+n-1]之间的唯一随机数。使用拒绝抽样很容易实现 - 如果选择了两次同一个数字，只需舍弃它并选择另一个数字。

将它们排序，然后计算每个X之间的o的数量。这个数量等于currentValue - previousValue - 1。

---

最后，这里有一些示例Java代码（未经测试），可以实现这个功能：

private List<long> getRandomSequenceWithSum(int numValues, long sum)
{
    List<long> xPositions = new List<long>();
    List<long> solution = new List<long>();
    Random rng = new Random();

    //Determine the positions for all the x's
    while(xPositions.size() < numValues-1)
    {
        //See https://dev59.com/xXE85IYBdhLWcg3w64EA#2546186
        //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;
}

- BlueRaja - Danny Pflughoeft

---

你可以通过将区间（在你的情况下是“o”的连续段）按内部“o-o”边界数量加权来选择区间，从而避免使用拒绝抽样（在某些边缘情况下变得非常棘手）。例如，如果你像这样分割你的总和 ooooXoXoo，你有3个区间，第一个区间的权重为3，第二个区间的权重为0，第三个区间的权重为1。因此，从1到4中选择一个数字将让你选择要分割的位置。（这基本上是我在上面回答中概述的方法）。 - Michael Anderson

Answer 4

一个好的方法是使用一个区间列表，然后在每个步骤中将其分割。以下是伪代码：

 array intervals = [(0,M)]
   while number intervals<desired_number
     pick an split point x
     find the interval containing x
     split that interval at x

如果您想非常小心，您需要检查分割点 x 是否不是区间的端点。您可以通过拒绝法来做到这一点，或者您可以选择要拆分的区间，然后选择在哪里拆分该区间，但在这种情况下，您需要小心不要引入偏差。（如果您关心偏差）。

- Michael Anderson

Answer 5

我相信你的问题在于Math.round，尝试修改你的代码使用双精度浮点数，避免任何精度损失。

- RyanS

Answer 6

这样怎么样：

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;

换句话说，将所有的舍入误差放入第一个元素中。

- QuantumMechanic

Answer 7

建议：

  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循环。

- Tejas Patil

Answer 8

取一个数字。从中减去一个合理的随机数。重复此过程，直到获得足够的数字。它们的总和根据定义是固定的，并且等于初始数字。您将进行确切的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

它可以工作，但有一个缺点：数字越远，它们就越小。你可能需要打乱结果列表来解决这个问题，或者尝试使用更小的上限。

- 9000

Answer 9

这确实是一个有趣的问题（点赞！），我期待看到更多创意解决方案。我对你列出的代码有一个问题，那就是你使用了Random类，它只返回整数，而不是长整型，但是你又将其强制转换为长整型。所以如果你的函数真的需要长整型，你就必须找到一个不同的随机数生成器。

“理想”的解决方案是生成所有可能的加法组合（称为分区），然后随机选择一个。然而，目前已知的执行此操作的最佳算法非常昂贵。关于这个问题，有很多好的资料可供参考。以下是一个特别好的分区算法阅读材料：

http://www.site.uottawa.ca/~ivan/F49-int-part.pdf

问题的一部分是要确定在这种情况下你所说的“随机”的含义。例如，如果你正在寻找一个包含5个数字且总和为1000的数组，那么{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，只是为了方便创建一个新的，但现在我可以传入一个种子随机数生成器，并且如果需要，生成相同的结果，这对于测试非常有用。每当您有一个使用随机数生成器的方法时，我强烈建议采用这种方法。

该算法基本上会将随机数添加到数组中的随机条目中，直到达到所需的总和。由于它的加性特性，它会偏向较大的数字（即，结果中出现小数字的可能性极小）。然而，这些数字将呈现出随机性，并且它们将适当地求和。

如果您的目标数字很小（比如小于100），您实际上可以采用真正的随机方法来生成所有分区并随机选择一个。例如，这是一个分区算法（由http://homepages.ed.ac.uk/jkellehe/partitions.php提供，已翻译成C#）：

public List<int[]> GetPartitions( int n ) {
var result = new List<int[]>();
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)表示从数组a中取出前x个元素...我相信现在Java中有一些等效的魔法可以做到这一点。）

这将返回一个分区列表...随机选择一个，您将拥有完美的随机分布。

- Ethan Brown

Answer 10

-这个怎么样？

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

- shem