生成m [0..n-1]范围内的m个不同随机数

Question

我有两种方法在[0..n-1]范围内生成m个不同的随机数

方法1:

//C++-ish pseudocode
int result[m];
for(i = 0; i < m; ++i)
{
   int r;
   do
   {
      r = rand()%n;
   }while(r is found in result array at indices from 0 to i)
   result[i] = r;   
}

方法2:

//C++-ish pseudocode
int arr[n];
for(int i = 0; i < n; ++i)
    arr[i] = i;
random_shuffle(arr, arr+n);
result = first m elements in arr;

当n远大于m时,第一种方法更有效,而第二种方法则更有效.但"更大"并不是一个严格的概念,是吗？:)

问题:我应该使用什么公式n和m来确定method1或method2是否更有效？(根据运行时间的数学期望)

Answer 1

纯数学:
让我们计算rand()两种情况下函数调用的数量并比较结果:

案例1:i = k当你已经选择了k个数字时, 让我们看看步骤中呼叫的数学期望.通过一次rand()调用获得数字的概率等于p = (n-k)/n.我们需要知道这种呼叫数量的数学期望,这导致获得我们还没有的数字.

使用1呼叫获取它的概率是p.使用2电话 - q * p,在哪里q = 1 - p.一般情况下,在n通话之后准确获得它的概率是(q^(n-1))*p.因此,数学期望是
Sum[ n * q^(n-1) * p ], n = 1 --> INF.这个总和等于1/p(由wolfram alpha证明).

因此,在该步骤中,i = k您将执行1/p = n/(n-k)该rand()函数的调用.

现在让我们总结一下:

Sum[ n/(n - k) ], k = 0 --> m - 1 = n * T-数量rand方法1中调用
这里T = Sum[ 1/(n - k) ], k = 0 --> m - 1

案例2:

这里rand()称为内部random_shuffle n - 1时间(在大多数实现中).

现在,要选择方法,我们必须比较这两个值:n * T ? n - 1.
因此,要选择合适的方法,请按T上述方法计算.如果T < (n - 1)/n最好使用第一种方法.否则使用第二种方法.

Answer 2

查看原始Fisher-Yates算法的维基百科描述.它主张基本上使用方法1最多为n/2,而方法2则用于其余部分.

Answer 3

就个人而言,我会使用方法1,然后如果M> N/2,选择NM值,然后反转数组(返回未选中的数字).因此,例如,如果N为1000并且您想要950个,则使用方法1选择50个值,然后返回另一个950.

编辑:虽然,如果一致的性能是你的目标,我会使用一个修改后的方法2,它不会完全洗牌,但只会改组N长度数组的前M个元素.

int arr[n];
for(int i = 0; i < n; ++i)
    arr[i] = i;

for (int i =0; i < m; ++i) {
   int j = rand(n-i); // Pick random number from 0 <= r < n-i.  Pick favorite method
   // j == 0 means don't swap, otherwise swap with the element j away
   if (j != 0) { 
      std::swap(arr[i], arr[i+j]);
   }
}
result = first m elements in arr;

Answer 4

这是一个算法,它可以在O(n)内存和O(n)时间(其中n是返回结果的数量,而不是你选择的集合的大小)适用于任何结果集.它是用Python方便的,因为它使用了哈希表:

def random_elements(num_elements, set_size):
    state = {}
    for i in range(num_elements):
        # Swap state[i] with a random element
        swap_with = random.randint(i, set_size - 1)
        state[i], state[swap_with] = state.get(swap_with, swap_with), state.get(i, i)
    return [state[i] for i in range(num_elements) # effectively state[:num_elements] if it were a list/array.

这只是一个部分渔民洗牌,数组被洗牌实现为稀疏哈希表 - 任何不存在的元素都等于其索引.我们将第一个num_elements索引洗牌,然后返回这些值.在set_size = 1,这相当于在该范围内挑选随机数的情况下,并且在这种情况下num_elements = set_size,这相当于标准的渔民洗牌.

观察到这是O(n)时间并且因为循环的每次迭代在哈希表中初始化最多两个新索引,它也是O(n)空间,这是微不足道的.