我有一个包含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,但伪代码中的描述可能仍然有用.
给定两个整数N和n(N> = n> 0),如何生成长度= n的[0,N]的随机选择(不重复!)？例如,给定N = 5,n = 3个可能的解是(3,0,2)或(2,4,1)等.
有一个限制,阻止使用天真的方法:内存使用必须是O(n),而不是O(N).
/*在天真的方法下,我的意思是使用大小= N的临时数组,它最初按顺序用数字0..N-1填充.从该数组中随机选择所需的n个项目.*/
可能重复:
如何有效地生成0和上限N之间的K个非重复整数列表
有什么替代方法可以生成[0,8000]范围内的1000个不同的随机整数,而不是以下方法:
我需要生成满足以下要求的字符串:
我会在生成后将它们存储在数据库中(它们将被分配给其他实体).
我的意图是做这样的事情:
我对该算法的关注是它不保证有限时间内的结果(如果数据库中已经有很多值).
问题:您能否就如何改进此算法提供更具确定性的建议？
谢谢.
假设我有一个数据列表:{1,2,3,4,5,6,7,8,9,10}其中n = 10个元素
我想随机选择这个集合的k个元素来形成一个子列表,比如k = 5.
在那种情况下,我最终会得到一个看起来像{9,3,5,2,7}的子列表
我能做到这一点:
这个问题是,随着原始列表的增长,偏移量和删除时间也会增长,对于任何非常大的列表(例如超过1,000,000个元素),执行此算法需要相当长的时间.
有没有更快的方法从给定数据列表生成随机序列？应该为这个问题留出随机数发生器的实现,而是关注如何在提出的算法中使用RNG结果.
有什么想法吗？
现在我正在使用C++ STL列表
我需要从Scala中的列表中随机抽取n个元素的子集,我想知道是否有一种方便的方法可以这样做,而无需手动检查n个元素中的每一个都是唯一的.目前我有这样的事情:
import util.Random
def sample(itms:List[A], sampleSize:Int) {
var numbersSeen = Set[Int]()
var sampled = List[A]()
val itmLen = itms.size()
var sampleIdex = Random.nextInt(itmLen)
while(sampled < sampleSize) {
if(numbersSeen.contains(sampleIdex)){
sampleIdex = Random.nextInt(itmLen)
} else {
numbersSeen.add(sampleIdex)
sampled.add(itms(sampleIdex))
}
}
sampled
}
我希望有更多的东西优雅可以做要么产生在一个范围内的整数的非重复随机列表或随机样本n从一个列表中的元素.
可能重复:
创建无重复的随机数序列
我想写一个只使用数字作为短字符串的URL缩短器.
我不想数数,我希望下一个新数字是随机的(或伪随机).
首先,思想算法看起来像这样(伪代码):
do
{
number = random(0,10000)
}
while (datastore.contains(number))
datastore.store(number, url)
此实现的问题是:由于数据存储区包含更多数字,因此循环将多次执行的可能性越大.性能会随着时间的推移而降低.
是否有更好的方法来获取尚未使用的随机数？
我正在尝试使用数组来修正一个程序,它可以获得0到24之间的随机数,但它们只能出现一次.我知道如何生成随机数,我只是坚持如何检查数字中是否已存在数字.我尝试生成一个新的rand()%25并将其与数组中的占位符进行比较,如果它不存在则将新的随机数放在那里,但它不起作用.
void MultiU (){
int size = 5;
int array[5];
srand(time(0));
for (int index = 0; index < size; index++){
exists[index] = rand() %25;
}
}
我是使用数组和rand()进行编程的新手.我希望有人可以指导我朝着正确的方向前进.