是否有一种有效的方法来生成具有给定总和或平均值的范围内的随机整数的组合? [英] Is there an efficient way to generate a combination of random integers in a range that have a given sum or average?

问题描述

是否存在一种有效的方法来生成N个整数的随机组合，从而使

Is there an efficient way to generate a random combination of N integers such that—

• 每个整数在区间[min，max]，
中
• 整数组合的总和为sum，并且
• 从满足其他要求的所有组合中随机选择一个统一的组合吗?

• each integer is in the interval [min, max],
• the combination of integers has a sum of sum, and
• the combination is chosen uniformly at random from among all combinations that meet the other requirements?

(如果是sum = N * mean，则选择平均值为mean的适当组合.)

(Choosing an appropriate combination with a mean of mean is a special case, if sum = N * mean.)

我知道可以通过以下方式解决此问题:

I am aware that this problem can be solved in the following way:

1. 使用Smith和Tromble中提供的算法( "Unit Simplex"(2004年)生成N个随机非负整数，总和为sum - N * min.

1. Use the algorithm given in Smith and Tromble ("Sampling from the Unit Simplex", 2004) to generate N random non-negative integers with the sum sum - N * min.

将min添加到以此方式生成的每个数字中.

Add min to each number generated this way.

但是，如果max远小于sum，则此算法速度较慢.例如，根据我的测试(使用上述涉及mean的特殊情况的实现)，该算法平均拒绝了

However, this algorithm is slow if max is much less than sum. For example, according to my tests (with an implementation of the special case above involving mean), the algorithm rejects, on average—

• 如果N = 7, min = 3, max = 10, sum = 42，则大约有1.6个样本，但是
• 如果N = 20, min = 3, max = 10, sum = 120，则大约有30.6个样本.

• about 1.6 samples if N = 7, min = 3, max = 10, sum = 42, but
• about 30.6 samples if N = 20, min = 3, max = 10, sum = 120.

是否有一种方法可以修改此算法，使其对大氮有效，同时仍满足上述要求?

Is there a way to modify this algorithm to be efficient for large N while still meeting the requirements above?

以下代码示例是用Ruby提供的，但我的问题与编程语言无关:

The following code example is given in Ruby, but my question is independent of programming language:

def posintwithsum(n, total)
    raise if n <= 0 or total <=0
    ls = [0]
    ret = []
    while ls.length < n
      c = 1+rand(total-1)
      found = false
      for j in 1...ls.length
        if ls[j] == c
          found = true
          break
        end
      end
      if found == false;ls.push(c);end
    end
    ls.sort!
    ls.push(total)
    for i in 1...ls.length
       ret.push(ls[i] - ls[i - 1])
    end
    return ret
end

def integersWithSum(n, total)
 raise if n <= 0 or total <=0
 ret = posintwithsum(n, total + n)
 for i in 0...ret.length
    ret[i] = ret[i] - 1
 end
 return ret
end

# Generate 100 combinations
mn=3
mx=10
sum=42
n=7
100.times {
 while true
    pp=integersWithSum(n,sum-n*mn).map{|x| x+mn }
    if !pp.find{|x| x>mx }
      p pp; break # Output the sample and break
    end
 end
}

推荐答案

我尚未对此进行测试，因此它并不是真正的答案，只是尝试尝试的时间太长而无法放入评论中.从满足前两个条件的数组开始，并继续使用它，以便它仍然满足前两个条件，但是随机性更高.

I have not tested this, so it is not really an answer, just something to try which is too long to fit into a comment. Start with an array which meets the first two criteria and play with it so it still meets the first two, but is a lot more random.

如果平均值是整数，则您的初始数组可以是[4，4，4，4，... 4]，也可以是[3，4，5，3，4，5，... 5，8， 0]或类似的简单内容.平均为4.5，请尝试[4，5，4，5，... 4，5].

If the mean is an integer, then your initial array can be [4, 4, 4, ... 4] or maybe [3, 4, 5, 3, 4, 5, ... 5, 8, 0] or something simple like that. For a mean of 4.5, try [4, 5, 4, 5, ... 4, 5].

接下来，在数组中选择一对数字num1和num2.可能应该按照顺序选择第一个数字，就像使用Fisher-Yates混洗一样，应该随机选择第二个数字.按顺序排列第一个数字可确保每个数字至少被选择一次.

Next pick a pair of numbers, num1 and num2, in the array. Probably the first number should be taken in order, as with the Fisher-Yates shuffle, the second number should be picked at random. Taking the first number in order ensures that every number is picked at least once.

现在计算max-num1和num2-min.这些是从两个数字到max和min边界的距离.将limit设置为两个距离中较小的一个.这是允许的最大更改，不会将一个或另一个数字超出允许的限制.如果limit为零，则跳过该对.

Now calculate max-num1 and num2-min. Those are the distances from the two numbers to the max and min boundaries. Set limit to the smaller of the two distances. That is the maximum change allowed which will not put one or other of the numbers outside the allowed limits. If limit is zero then skip this pair.

选择[1，limit]范围内的随机整数:将其称为change.我在可选取范围内省略了0，因为它没有作用.测试可能表明，通过包含随机性，您可以获得更好的随机性；我不确定.

Pick a random integer in the range [1, limit]: call it change. I omit 0 from the pickable range as it has no effect. Testing may show that you get better randomness by including it; I'm not sure.

现在设置num1 <- num1 + change和num2 <- num2 - change.这不会影响平均值，并且数组的所有元素仍在所需的边界内.

Now set num1 <- num1 + change and num2 <- num2 - change. That will not affect the mean value and all elements of the array are still within the required boundaries.

您将需要至少遍历整个数组一次.测试应该显示您是否需要多次进行操作才能获得足够随机的内容.

You will need to run through the whole array at least once. Testing should show if you need to run through it more than once to get something sufficiently random.

这篇关于是否有一种有效的方法来生成具有给定总和或平均值的范围内的随机整数的组合?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！