代码之家 › 专栏 › 技术社区 › Adel Redjimi

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

probability random numpy python

Adel Redjimi · 技术社区 · 8 年前

任务:

生成一对随机数 (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)

附言:这不是家庭作业,我正在尝试使用随机优化技术,使用交换操作生成随机邻居。

3 回复 | 直到 8 年前

tobias_k 8 年前

这个怎么样?

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

范围内1000000对的随机分布 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(klogk)。

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 和1000000次迭代,结果看起来是正确的。

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

Daniel F 8 年前

我将上面的@tobias\u 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

ybeltukov 7 年前

从Numpy 1.7.0开始,您可以使用 np.choice 具有 replace=False :

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

以下是10000个样本的分布情况: