在约束条件下生成离散随机数

Question

我有一个问题，我不知道如何正确解决。

假设我们必须生成1 <= n <= 40数字:X[1], X[2], ..., X[n].

对于每一个数字，我们都有一个离散的空间，我们可以从中画出一个数字。该空间并不总是一个范围，可以相当大(数千/数百万个数字)。

另一个约束是生成的数字数组应该按升序排序:X[1] <= X[2] <= ... <= X[n].

作为三个数字的例子:

X[1] in {8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}

X[2] in {10, 20, 30, 50}

X[3] in {1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003}

该测试的有效输出示例:[9, 20, 2001],[18, 30, 1995]

该测试的无效输出示例:[25, 10, 1998](不递增顺序)

我已经尝试了不同的方法，但我不满意的是，它们都产生了不均匀分布的结果，也就是说，我所有的解决方案都有很强的偏差，一些样本代表性不足。

其中一种方法是尝试逐个随机生成数字，并在每次迭代中减少即将出现的数字的空间，以满足递增顺序条件。这很糟糕，因为这个解决方案总是将最后的数字偏向于可能范围的高端。

我已经放弃了寻找一个可以均匀产生样品的精确解。我真的很感激任何合理的解决方案(最好是在Python上，但什么都可以，真的)。

Answer 1

我不会为你编写代码，但这里是执行非蛮力方法的逻辑:

定义N(i,x)为x的可能样本数[1]，…，其中X[i]= X。S(i)是X[i]的可能值。递归式N(i,x) = S(i-1)中y =x (N(i-1,y))对y求和。这可以让你快速计算出所有的N(i,x)然后很容易从末尾构建您的样本:

知道所有的N(N,x)，你可以从S(N)中以N(N,x [N])/(S (N)中N(N,x)对x求和)的概率画出x [N]

然后你继续往下画:给定你已经画了X[n]，X[n-1]，…，X[i+1]你从S(i)中画出X[i]，X[i] <=X[i+1]，概率为N(i,X[i])/(S (i)中X的总和，X <=X[i+1] (N(i,X))

Answer 2

这是我在评论中建议的hueristic的实现:

import random
def rand_increasing(sets):
#assume: sets is list of sets
sets = [s.copy() for s in sets]
n = len(sets)
indices = list(range(n))
random.shuffle(indices)
chosen = [0]*n
for i,k in enumerate(indices):
chosen[k] = random.choice(list(sets[k]))
for j in indices[(i+1):]:
if j > k:
sets[j] = {x for x in sets[j] if x > chosen[k]}
else:
sets[j] = {x for x in sets[j] if x < chosen[k]}
return chosen
#test:
sets = [{8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31},
{10, 20, 30, 50},
{1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003}]
for _ in range(10):
print(rand_increasing(sets))

典型输出:

[24, 50, 1996]
[26, 30, 2001]
[17, 30, 1995]
[11, 20, 2000]
[12, 20, 1996]
[11, 50, 2003]
[14, 20, 2002]
[9, 10, 2001]
[8, 30, 1999]
[8, 10, 1998]

当然，如果你可以用朱利安的方法得到均匀的抽样，那就更好了。(这个启发式可能给出统一——但这需要证明)。还要注意，在早期阶段的糟糕选择可能会导致排列中的一些后期集合为空，从而引发错误。该函数可以在带有适当错误捕获的循环中调用，从而产生一种不命中即失败的方法。