通过均匀分布的RNG生成3个不同的随机整数 [英] Generate 3 distinct random integers via a uniformly distributed RNG

问题描述

假设我有一个 randint(A，B)函数，该函数会在(包括)范围 [A，B] 中生成均匀分布的随机整数.例如， 1< = randint(1，10)< = 10 .如何有效地在一定范围内随机生成3个不同的整数?

Suppose I have a randint(A, B) function which generates a uniformly distributed random integer in the (inclusive) range [A, B]. For example, 1 <= randint(1, 10) <= 10. How can I efficiently randomly generate 3 distinct integers within a certain range?

应该通过对 randint(A，B) 的3次调用来完成此操作.我不在乎我得到的三个数字是哪个排列；它可以是随机的，也可以具有定义的顺序.

This should be done with exactly 3 calls to randint(A, B). I don't care which permutation of the three numbers I get; it can be random or have a defined order.

我不仅在尝试找到任何算法来做到这一点，而且(在合理的情况下)使用最少的额外内存的最快算法.

I'm not just trying to find any algorithm to do this, but (within reason) the fastest ones which use the least additional memory.

def rand3(low, high):
    assert high - low + 1 >= 3
    # Magic!
    return n1, n2, n3 # each number has low <= n <= high, each number is distinct

---

最简单的方法(尽管非常昂贵)是生成一个数字列表， [low，low + 1，...，high] ，然后将Fisher-Yates随机播放到选择3个元素.不必全面评估Fischer-Yates，因为我们可以滚动三个索引.但是，我绝对不想在内存中创建此数组.

---

The easiest way to do this, albeit very expensive, is to generate a list of numbers [low, low + 1, ..., high], then do the Fisher-Yates shuffle to select 3 elements. It's not necessary to fully evaluate Fischer-Yates, as we can just roll three indices. However, I definitely do not want to create this array in memory.

对于2个整数，足以将第二个整数滚动到小于一个的范围内，如果大于或等于第一个数字，则向上调整其值:

For 2 integers, it suffices to roll the second integer in the range less one, adjusting its value upward if it's greater than or equal to the first number:

def rand2(low, high):
    i1 = randint(low, high)
    i2 = randint(low, high - 1)
    n1 = i1
    n2 = i2 + (i2 >= n1)
    return n1, n2

但是，将其扩展为三个整数并非易事.我相信应该可以做这样的事情:

However, it's not straightforward to extend this to three integers. I believe it should be possible to do something like this:

# I _think_ this works?
def rand3(low, high):
    i1 = randint(low, high)
    i2 = randint(low, high - 1)
    i3 = randint(low, high - 2)

    n1 = i1
    n2 = i2 + (i2 >= n1)
    if n1 > n2: n1, n2 = n2, n1
    n3 = i3 + (i3 >= n1)
    n3 = n3 + (n3 >= n2)

    return n1, n2, n3

但是，我觉得必须要比这简单一些.3元素问题真的要复杂得多，我们需要对2个整数进行排序，而第二个条件( n3> = n2 )必须取决于中间值 n3 ?我期待的是更接近2元素问题的东西.

However, I feel like there has to be something simpler than this. Is the 3 element problem really that much more complex that we need to sort the 2 integers and that the second conditional (n3 >= n2) must depend on an intermediate value of n3? I was expecting something much closer to the 2 element problem.

推荐答案

我不知道这些变化是否会让您更快乐，但是此 rand3 至少少了一个比较.

I don't know if these variations make you happier, but this rand3 has one fewer comparison at least.

这个想法是模拟费舍尔·耶茨的几个步骤.在 rand3 中，我们从索引 i3 开始反向查找值.第一个 if 撤消第二个交换，第二个 if 撤消第一次交换.

The idea is to simulate a couple steps of Fisher--Yates. In rand3, we work backward from the index i3 to find the value. The first if undoes the second swap, and the second if undoes the first swap.

import collections
from random import randint


def rand2(low, high):
    i1 = randint(low, high)
    i2 = randint(low, high - 1)
    if i2 == i1:
        i2 = high
    return i1, i2


def rand3(low, high):
    i1 = randint(low, high)
    i2 = randint(low, high - 1)
    i3 = randint(low, high - 2)
    if i3 == i2:
        i3 = high - 1
    if i3 == i1:
        i3 = high
    if i2 == i1:
        i2 = high
    return i1, i2, i3


print(collections.Counter(rand3(1, 4) for i in range(1000000)))

这篇关于通过均匀分布的RNG生成3个不同的随机整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！