统一生成不同整数的随机对

Question

任务:

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

第一次尝试

恒定的时间？YES.均匀分布？没有

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

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

样本可视化(不均匀分布)

您可以轻松地将限制的效果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)

可视化样本:

样本可视化(均匀分布)

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

相反的交换x用max,我们也可能会改变所有的值y,如果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和high1,000,000迭代,结果看起来是正确的.

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