相关疑难解决方法(0)

写一个函数有:

input: array of pairs (unique id and weight) length of N, K =< N  
output: K random unique ids (from input array)  

注意:在输出中多次出现某些Id的频率被调用的次数应该越多,它的权重就越大.示例:权重为5的id应出现在输出中比id为1的频率多5倍.此外,分配的内存量应在编译时知道,即不应分配额外的内存.

我的问题是:如何解决这个问题？

编辑
感谢大家的回复!
目前我无法理解对的重量如何影响输出对的出现频率,你能给我更清楚,"虚拟"解释它是如何工作的吗？

假设我想生成一个包含 1000 个唯一数字的随机列表（数字可以是 1 到 1000 的范围）。我可以通过将范围从 1 到 1000 扩展到实际列表，然后随机打乱元素来做到这一点。语言并不重要，但在 python 中它可能是这样实现的：random.shuffle(list(range(1000)))。

但是，如果我需要生成 100 亿个数字怎么办？将范围扩展到列表将需要大量内存（如果以 8 字节存储数字，则大约需要 74 GB 内存）。洗牌还需要大量的内存和时间。但并不需要一次生成所有的数字，而是最好一个一个地生成，保存状态，而不是存储所有数字而填满内存，而只存储一个。

数字仍然需要唯一。有没有用于此目的的算法？

如果有一种方法可以在给定的生成步骤中快速恢复生成器的“状态”，那就太好了。例如，如果我已经生成了 100 万个数字，而下一个数字必须是 10，那么如果我能够有效地（无需再次重新生成该百万个数字）以 100 万为步长恢复状态并生成下一个数字，那就太好了 - 10.

有这样的算法吗？

我目前正在尝试实现一种算法来选择唯一的(16位)标识符.挑战是以不使用太多内存的快速方式执行此操作.当前使用的标识符列表是通过一系列SPI事务扫描外部闪存设备来确定的,因此是一个相对较慢的过程.此外,该算法将在小型微控制器上运行,因此我不能真正将所有条目读入RAM并在那里处理它们.

到目前为止我的想法是:

1. 选择一个数字,然后扫描列表,看看它是否被使用.冲洗并重复.遭受相当缓慢(特别是如果有很多文件).
2. 如上所述,但是使用具有适当种子的伪随机数生成器来选择数字.这具有以下优点:不太可能存在如此大量的迭代.
3. 扫描列表并使用找到的所有条目填充数组.对它进行排序然后变得微不足道.这可能会占用大量内存.
4. 使用一个巨大的(好的,可笑的,巨大的)位掩码.不太实际.
5. 接受该工具的生命周期,使其在将65534个文件写入Flash之前很久就被丢弃或"格式化",因此只需将目前使用的最高值存储在Flash或备份内存中并继续增加.老实说,这可能对这个特定的应用程序非常有效.

目前,我正准备使用第二个或第五个,但我有兴趣知道是否有人有任何其他想法.我想认为有一种类似于CRC的算法,可以用来依次处理每个数字,并给出一个尚未使用的数字的公平概念,但我不知道这可能是怎样的工作.

可能重复:
如何有效地生成0和上限N之间的K个非重复整数列表

有什么替代方法可以生成[0,8000]范围内的1000个不同的随机整数,而不是以下方法:

1. 天真的方法:生成一个数字并检查它是否已经在数组中.为O(n ^ 2)
2. 线性shuffle:生成序列0到8000,shuffle,取第1000个.O(n)

我想通过使用Math.random生成6个不同的随机数并将它们存储到数组中.我怎样才能确保它们与众不同？我知道我需要使用for循环检查数组但是如何...

这是范围.我只需要1到49之间的数字.(1 +(int)(Math.random()*49))

我需要在C++中生成随机非重复数组,在这部分代码中我使用srand函数生成随机数,但有些数字是重复的.主要任务是为彩票生成随机数,所以我需要生成数字,直到标记为int golden的黄金数字.

#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;

int main()
{
  int golden = 31;
  int i = 0;
  int array[35];

 srand((unsigned)time(0));
    while(i != golden){
        array[i] = (rand()%75)+1;
        cout << array[i] << endl;
        i++;
}
 }

Run Code Online (Sandbox Code Playgroud)

我有一套455件物品,我随机选择最多160件物品,更换.首先我种子srand()然后rand()用来选择每个数字.我观察到,在我最多160件物品的选择中,我倾向于看到至少10件物品被选中不止一次.这似乎表明随机数不是均匀分布的.

有没有办法让更均匀分布的随机数？

我正在制作一个益智游戏,我想生成一个限制之间的随机数列表.我已经使用了rand和srand函数,但它也给了我重复的值.我想生成一个没有重复的随机列表我该怎么做？

我想生成1到10之间的随机数.当用户点击"下一步"按钮时,必须打印一个随机问题,并且不能重复问题.问题是,有时问题是重复.任何人都可以帮助我或提供一些参考或教程吗？

- (IBAction)nextQuestion:(id)sender
{
    NSInteger randomNum = arc4random() %10 ;
    int countCounter= counter++;
    [self.btnNext setTitle:@"Next" forState:UIControlStateNormal];

    if(countCounter==4)
    {
        self.btnNext.hidden=YES;
        self.btnQuizDone.hidden=NO;
    }

    switch ( arc4random()%10) 
    {
      case 0:
      {
          NSLog(@"zero");

          [lblQuestion setText:@"Q10:question number ten"];

      }
      break;
     case 1:
      {
          NSLog(@"one");
          [lblQuestion setText:@"Q2:question number two"];

      }
      break;
      case 2:
      {
          NSLog(@"two");
          [lblQuestion setText:@"Q6:question number six"];

      }
      break;
      case 3:
      {
          NSLog(@"three");
          [lblQuestion setText:@"Q5:question  number five"];

      }
       break;
      case 4:
      {
          NSLog(@"four");
          [lblQuestion setText:@"Q3:question number three"];

      }
      break;
      case 5:
      {
          NSLog(@"five");
          [lblQuestion …

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

我是Java新手.我想从给定的集合中生成一组随机数,并且数字也必须不重复.例如,可能的数字是[0,1,2,3],我想获得存储在数组中的三个随机唯一数字.防爆.[0,2,1], [2,3,1], [0,3,2]等等