相关疑难解决方法(0)

我想生成0到1000之间永远不会重复的唯一随机数(即6不会出现两次),但这并不是像以前的值的O(N)搜索那样.这可能吗？

我需要一个快速算法从通用列表中选择5个随机元素.例如,我想从a获得5个随机元素List<string>.

该问题给出了所有必要的数据:在给定区间[0,N-1]内生成一系列K个非重复整数的有效算法是什么.平凡算法(产生随机数,并把它们添加到序列,看着他们,看看他们是否已经在那里之前)是非常昂贵的,如果ķ大且足够接近ñ.

在从链表中有效地选择一组随机元素中提供的算法似乎比必要的更复杂,并且需要一些实现.我刚刚发现了另一种似乎可以完成工作的算法,只要您知道所有相关参数,只需一次通过即可.

可能重复:
O(1)中的唯一随机数？

如何在C中填充具有唯一值(无重复项)的整数数组？

int vektor[10];   

for (i = 0; i < 10; i++) {
    vektor[i] = rand() % 100 + 1;
}

//No uniqueness here

我想k在n没有选择相同数字两次的情况下随机选择均匀的元素.这有两个简单的方法.

1. 列出所有n可能性.将它们洗牌(你不需要通过执行Fisher Yates的第一步来改变它们的 所有n数字).选择第一个.这种方法需要时间(假设分配一个大小的数组需要 时间)和空间.如果相对于非常小,这是一个问题.kkkO(k)nO(1)O(n)kn
2. 存储一组看到的元素.从中随机选择一个数字[0, n-1].当元素在集合中时,然后选择一个新数字.这种方法占用O(k)空间.运行时分析要复杂一些.如果k = theta(n)那时运行时间是 O(k*lg(k))=O(n*lg(n))因为它是优惠券收集器的问题.如果k相对较小n则需要稍微多于O(k)因为选择相同数字两次的概率(尽管很低).这在空间方面优于上述解决方案,但在运行时方面更差.

我的问题:

是否有O(k)时间,O(k)空间算法为所有k和n？

I need a way to sample without replacement a certain array a. I tried two approaches (see MCVE below), using random.sample() and np.random.choice.

I assumed the numpy function would be faster, but it turns out it is not. In my tests random.sample is ~15% faster than np.random.choice.

Is this correct, or am I doing something wrong in my example below? If this is correct, why?

import numpy as np
import random
import time
from contextlib import contextmanager …

我正在寻找最有效的算法来随机选择一组n个不同的整数,其中所有整数都在某个范围[0..maxValue].

约束:

• maxValue大于n,可能更大
• 我不在乎输出列表是否排序
• 必须以相同的概率选择所有整数

我最初的想法是构造一个整数列表[0..maxValue]然后随机提取n个元素而不替换.但这似乎效率很低,特别是如果maxValue很大的话.

更好的解决方案？

我有以下代码$n从$arrayPHP中的数组中选择元素:

shuffle($array);
$result = array_splice($array, 0, $n);

给定一个大数组但只有少数元素(例如5out 10000),这是相对较慢的,所以我想优化它,以便不是所有元素都必须被洗牌.值必须是唯一的.

我正在寻找最有效的替代方案.我们可以假设$array没有重复并且是0索引的.

我正在使用Python并且正在使用numpy.我想生成一对随机数.我想排除对的重复结果,两个条目都是相同的数字,我想包括只有一个条目是相同数字的对.我试图使用

import numpy
numpy.random.choice(a,(m,n),replace=False) 

对于它,但它完全排除任何具有相同条目的tupels,即

import numpy
numpy.random.choice(a=2,(m=2,n=1),replace=False) 

只给我(1,0)和(0,1)而不是(1,1),(0,0),(1,0)和(0,1).

我想这样做是因为我想绘制一个随机元组的样本,其中包含大的a和大的n(如上所述),而不会获得完全相同的tupels.它也应该或多或少有效.有没有一种方法可以实现这一点？

我有一个包含n个元素的外部集合,我想随机选择它们中的一些数字(k),将这些元素的索引输出到某个序列化数据文件.我希望索引以严格的升序输出,并且没有重复.n和k都可能非常大,并且将整个数组简单地存储在该大小的存储器中通常是不可行的.

我想出的第一个算法是从1到nk中选择一个随机数r [0] ...然后从r [i-1] +1到n-k + i中选择一个连续的随机数r [i] ,只需要在任何时候为'r'存储两个条目.然而,一个相当简单的分析表明,选择小数的概率与整个集合均匀分布时的概率不一致.例如,如果n是十亿而k是五亿,那么用我刚刚描述的方法选择第一个条目的概率非常小(五分之一十亿),实际上,因为一半条目是被选中,第一个应该在50%的时间被选中.即使我使用外部排序来对k个随机数进行排序,我也不得不丢弃任何重复项,然后再试一次.当k接近n时,重试次数将继续增加,不保证终止.

如果可能的话,我想找到一个O(k)或O(k log k)算法来做这个.我将使用的实现语言是C++ 11,但伪代码中的描述可能仍然有用.