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

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    + + + + + +   + + + + + + + +
                                  \-------------->

0..5

范围内 1,000,000 对的随机分布

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 和 high 的小值和 1,000,000 次迭代再次测试，结果看起来正确。

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

Answer 2

我把上面@tobias_k的方法扩展到k个值。

def uni_repl(n, k, s = 1000):
    x = np.empty((k, s), dtype = int)
    for i in range(k):
        x[i] = np.random.randint(low = 0, high = n - k + i + 1, size = s)
    for i in range(1, k):
        x[:i][x[:i] == x[i]] = n - k + i
    return x

测试：

test = np.zeros((5,5,5))

np.add.at(test, list(uni_repl(5, 3)), 1)

test
Out[85]: 
array([[[     0.,      0.,      0.,      0.,      0.],
        [     0.,      0.,  16304.,  16767.,  16622.],
        [     0.,  16418.,      0.,  16631.,  16517.],
        [     0.,  16688.,  16607.,      0.,  16495.],
        [     0.,  16663.,  16544.,  16877.,      0.]],

       [[     0.,      0.,  16736.,  16767.,  16668.],
        [     0.,      0.,      0.,      0.,      0.],
        [ 16862.,      0.,      0.,  16634.,  16632.],
        [ 16791.,      0.,  16689.,      0.,  16557.],
        [ 16566.,      0.,  16843.,  16864.,      0.]],

       [[     0.,  16737.,      0.,  16638.,  16437.],
        [ 16741.,      0.,      0.,  16545.,  16617.],
        [     0.,      0.,      0.,      0.,      0.],
        [ 16804.,  16923.,      0.,      0.,  16598.],
        [ 16756.,  16850.,      0.,  16778.,      0.]],

       [[     0.,  16777.,  16675.,      0.,  16760.],
        [ 16454.,      0.,  16792.,      0.,  16669.],
        [ 16476.,  16709.,      0.,      0.,  16677.],
        [     0.,      0.,      0.,      0.,      0.],
        [ 16680.,  16863.,  16640.,      0.,      0.]],

       [[     0.,  16459.,  16446.,  16756.,      0.],
        [ 16637.,      0.,  16626.,  16756.,      0.],
        [ 16481.,  16773.,      0.,  16762.,      0.],
        [ 16754.,  16531.,  16681.,      0.,      0.],
        [     0.,      0.,      0.,      0.,      0.]]])

与使用np.argpartition的方法相比，这似乎更快，只要k < 0.4 * n

def uni_part(n, k, s = 1000):
    x = np.random.rand(n, s)
    return np.argpartition(x, k, axis = 0)[:k]

%timeit uni_part(100, 40)
100 loops, best of 3: 3.93 ms per loop

%timeit uni_repl(100, 40)
100 loops, best of 3: 3.76 ms per loop

%timeit uni_part(100, 10)
100 loops, best of 3: 3.55 ms per loop

%timeit uni_repl(100, 10)
1000 loops, best of 3: 425 µs per loop

%timeit uni_part(100, 50)
100 loops, best of 3: 4.08 ms per loop

%timeit uni_repl(100, 50)
100 loops, best of 3: 4.89 ms per loop

Answer 3

从 Numpy 1.7.0 开始，您可以使用 np.choice 和 replace=False:

np.random.choice(10, 2, replace=False)
array([2, 6])

这里是 10000 个样本的分布：

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

Uniformly generating random pairs of different integers

python

random

numpy

probability

任务：

第一次尝试

第二次尝试