python - 均匀生成不同整数的随机对

Question

任务:

• 生成一对随机数(i,j)(顺序无关紧要:(i,j)等价于(j,i )).
• 该对必须包含两个不同的值:i != j
• 成对必须均匀分布。换句话说，所有可能对的概率都相同。
• 在固定时间执行此操作。

第一次尝试

常数时间？ 是。均匀分布？ 否

x = np.random.randint(low=0, high=10 - 1)
y = np.random.randint(low=x + 1, high=10)

可视化样本(忽略顺序):

Samples visualization (not uniformly distributed)

您可以很容易地限制 y 大于 x 的效果，这意味着更高的对有更高的概率(这里的不透明度表示密度)。

第二次尝试

常数时间？ 否。均匀分布？ 是

x = np.random.randint(low=0, high=nbr_values)
y = np.random.randint(low=0, high=nbr_values)

while x == y:
  y = np.random.randint(low=0, high=nbr_values)

可视化样本:

Samples visualization (uniformly distributed)

PS:这不是家庭作业，我正在试验使用交换操作随机生成邻居的随机优化技术。

Answer 1

这个怎么样？

x = np.random.randint(low=0, high=nbr_values)
y = np.random.randint(low=0, high=nbr_values - 1)
if y == x:
    y = nbr_values

x 的值在所有可能值中平均分布，y 的值在所有剩余 值中平均分布, x 的当前值作为最大值(也可以是最小值，在这种情况下只需使用 low=1)。

图形近似:

range                 0 - - - - - - - - - - - - - MAX
distribution for x    + + + + + + + + + + + + + + +
random value for x                x
distribution for y    + + + + + +   + + + + + + + +
                                  \-------------->

1,000,000 对在 0..5 范围内的随机分布

0       33425   33147   33411   33340   33365
33206   0       33537   33568   33679   33317
33307   33284   0       33423   33121   33189
33235   33303   32970   0       33347   33316
33233   33946   33257   33272   0       33504
33517   33203   33394   33221   32963   0

---

如果 y >= x，即 if y >= x: y += 1，产生相同的分布。这样，通过将当前值与所有先前值进行比较并相应地将其向上移动，上述内容也可以推广到两个以上的值。不过，这需要对绘制的值进行排序，因此复杂度略高，大约为 O(k²logk)。

def draw(low, high, k):
    drawn = []
    for i in range(k):
        y = random.randint(low, high - i)
        for x in sorted(drawn):
            if y >= x:
                y += 1
        drawn.append(y)
    return drawn

用较小的 low 和 high 值以及 1,000,000 次迭代再次测试，结果看起来是正确的。

或者，您可以只使用 random.sample(range(low, high+1), k) .我不知道这是如何实现的，但它非常快，即使对于较大的上限值和接近最大值数的 k 也是如此。