c++ 在一个范围内生成N个随机数,且总和为常数

yizd12fk  于 2023-03-14  发布在  其他
关注(0)|答案(5)|浏览(213)

我想从[a,b]之间的特定分布(例如均匀随机)中生成N个随机数,这些随机数总和为常数C。我尝试了几种我自己能想到的解决方案,以及一些在类似线程上提出的解决方案,但其中大多数要么适用于有限形式的问题,要么我无法证明结果仍然遵循所需的分布。
我尝试过的:生成N个随机数,将它们除以它们的和,然后乘以所需的常数。这似乎可以工作,但结果不符合数字应在[a:b]范围内的规则。
生成N-1个随机数,加上0和所需的常数C,并对它们进行排序。然后计算每两个连续数之间的差,差就是结果。这又和到C,但有上一种方法相同的问题(范围可以大于[a:b])。
我还尝试生成随机数,并始终跟踪最小值和最大值,以保持所需的总和和范围,并得出以下代码:

bool generate(function<int(int, int)> randomGenerator,
              int min, int max, int len, int sum,
              std::vector<int> &output) {
    /**
     * Not possible to produce such a sequence
     */
    if (min * len > sum)
        return false;
    if (max * len < sum)
        return false;

    int curSum = 0;
    int left = sum - curSum;
    int leftIndexes = len - 1;
    int curMax = left - leftIndexes*min;
    int curMin = left - leftIndexes*max;

    for (int i = 0; i < len; i++) {
        int num = randomGenerator((curMin < min) ? min : curMin,
                                  (curMax > max) ? max : curMax);
        output.push_back(num);
        curSum += num;
        left = sum - curSum;
        leftIndexes--;
        curMax = left - leftIndexes * min;
        curMin = left - leftIndexes * max;
    }

    return true;
}

这似乎是工作,但结果有时是非常扭曲的,我不认为它是遵循原来的分布(例如均匀)。

//10 numbers within [1:10] which sum to 50:
generate(uniform, 1, 10, 10, 50, output);
//result:
2,7,2,5,2,10,5,8,4,5 => sum=50
//This looks reasonable for uniform, but let's change to 
//10 numbers within [1:25] which sum to 50:
generate(uniform, 1, 25, 10, 50, output);
//result:
24,12,6,2,1,1,1,1,1,1 => sum= 50

注意输出中有多少个1,这听起来很合理,因为范围更大,但它们看起来并不像是均匀分布的,我不确定是否有可能达到我想要的,也许是约束使问题无法解决。

wkyowqbh

wkyowqbh1#

如果您希望样本遵循均匀分布,则问题简化为生成N个sum = 1的随机数。反过来,这是狄利克雷分布的特例,但使用指数分布也可以更轻松地计算。
1.取所有vi均在0和1之间的均匀样本v1...vN。
1.对于所有i,1〈=i〈=N,定义ui:= -ln vi(注意ui〉0)。
1.将ui归一化为pi:= ui/s,其中s为u1+...+uN之和。
p1..pN是均匀分布的(在dim N-1的单纯形中),并且它们的和是1。
现在你可以把这些pi乘以你想要的常数C,然后把它们转换成另一个常数A的和,就像这样
齐:= A + π *C。

编辑3

为了解决评论中提出的一些问题,请允许我补充如下:

  • 为了确保最终的随机序列福尔斯在区间[a,B]内,选择上述常数A和C为A:= a和C:= b-a,即,取qi = a + pi*(b-a)。由于pi在范围(0,1)内,所有qi将在范围[a,b]内。
  • 如果vi碰巧为0,则不能取(负)对数-ln(vi),因为ln()未定义为0。这种事件的概率极低。然而,为了确保没有错误信号,上述第1项中v1... vN的生成必须以特殊方式处理任何0的出现:将-ln(0)视为+无穷大(记住:ln(x)-〉-infinity当x-〉0时)。因此和s = +infinity,这意味着pi = 1并且所有其他pj = 0。如果没有这个约定,序列(0...1...0)将永远不会生成(非常感谢@塞韦林Pappadeux的这个有趣的评论)。
  • 正如@Neil斯莱特在问题 * 的第4条注解中所解释的,逻辑上不可能满足原始框架的所有要求。因此,任何解决方案都必须将约束放宽到原始约束的适当子集。@Behrooz的其他注解似乎证实了这在这种情况下就足够了。
    编辑2

评论中又提出了一个问题:

  • 为什么重新标度均匀样本还不够?*

换句话说,* 我为什么要费心去取负对数?*
原因是,如果我们只是重新缩放,那么得到的样本将不会均匀地分布在线段(0,1)上(或最终样本的[a,b]上)。
为了形象化,让我们考虑2D,即,让我们考虑N=2的情况。均匀样本(v1,v2)对应于原点为的正方形中的随机点(0,0)和角(1,1)。现在,当我们归一化这样的点时,将其除以和s=v1+v2,我们所做的是将该点投影到对角线上,如图所示(记住对角线是x + y = 1):

但是考虑到绿色线,也就是离主对角线更近的(0,0)至(1,1)的投影线比橙子的投影线更长,橙色的投影线更靠近x轴和y轴,投影线的中心附近的投影倾向于聚集更多(蓝色),缩放后的样本位于其中。这表明简单的缩放不会在所示对角线上生成均匀的样本。另一方面,可以从数学上证明负对数确实能产生理想的均匀性。2因此,我不想复制粘贴数学证明,而是邀请每个人实现这两种算法,并检查得到的曲线是否如这个答案所描述的那样。
(**注:**这里有一篇关于这个有趣主题的博客文章,并应用于石油和天然气行业)

5sxhfpxr

5sxhfpxr2#

让我们试着简化这个问题,通过减去下界,我们可以把它简化为在**[0,b-a]中寻找N个数,使得它们的和为C-Na**。
重命名参数,我们可以在**[0,m]中查找N个数字,它们的和为S**。
现在,该问题类似于将长度为S的段划分为长度为**[0,m]N**个不同子段。
我认为这个问题根本无法解决。
如果S=1,N=1000并且m大于0,则唯一可能的重新划分是一个1和999个0,这与随机散布完全不同。

NmS之间存在相关性,即使选取随机值也不会使其消失。

对于最均匀的再分配,子段的长度将遵循平均值为S/N的高斯曲线。
如果你对随机数做不同的调整,你最终会得到任何偏差,但最终你永远不会同时得到均匀的[a,b]重划分和总长度C,除非你的[a,b]区间的长度恰好是2C/N-a。

dgiusagp

dgiusagp3#

对于我的答案,我将假设我们有一个均匀分布。
因为我们有一个均匀分布,所以C的每个元组都有相同的出现概率。例如,对于a = 2, b = 2, C = 12, N = 5,我们有15个可能的元组。从10开始,243开始,14开始。这给出了从115中选择一个随机数来选择第一个元素的想法。从110中,我们选择2。从1114,我们选择3,对于15,我们选择4

#include <time.h>
#include <random>

std::default_random_engine generator(time(0));
int a = 2, b = 4, n = 5, c = 12, numbers[5];

// Calculate how many combinations of n numbers have sum c
int calc_combinations(int n, int c) {
    if (n == 1) return (c >= a) && (c <= b);
    int sum = 0;
    for (int i = a; i <= b; i++) sum += calc_combinations(n - 1, c - i);
    return sum;
}

// Chooses a random array of n elements having sum c
void choose(int n, int c, int *numbers) {
    if (n == 1) { numbers[0] = c; return; }

    int combinations = calc_combinations(n, c);
    std::uniform_int_distribution<int> distribution(0, combinations - 1);
    int s = distribution(generator);
    int sum = 0;
    for (int i = a; i <= b; i++) {
        if ((sum += calc_combinations(n - 1, c - i)) > s) {
            numbers[0] = i;
            choose(n - 1, c - i, numbers + 1);
            return;
        }
    }
}

int main() { choose(n, c, numbers); }

可能结果:

2
2
3
2
3

这个算法对于大的N来说不能很好地扩展,因为在计算组合时会溢出(除非我们使用一个大的整数库),计算所需的时间以及需要任意大的随机数。

hgqdbh6s

hgqdbh6s4#

那么,对于n=10000,我们不能有一个小的数,不是随机的吗?
可能生成序列直到sum > C-max达到,然后只放入一个简单的数字来求和。
万分之一更像是系统中非常小的噪音。

f4t66c6m

f4t66c6m5#

虽然这是一个老主题,但我想我有一个想法。考虑我们想要N个随机数,其总和为C,每个随机数在a和b之间。为了解决问题,我们创建N个洞,并准备C个球,每次我们问每个洞“你想要另一个球吗?"。如果否,我们传递到下一个洞,否则,我们把一个球放进洞。每个洞有一个上限值:b-a.如果某个孔达到上限值,则总是传递到下一个孔。
示例:
0和2之间的3个随机数,其和为5。
模拟结果:
第1次运行:-+-
第2次运行:++-
第3次运行:---
第4次运行:+*+
最终:221

  • :垃圾球
    +:接受焊球
  • :完全通过

相关问题