相关疑难解决方法(0)

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

在这种情况下,MAX只有5,所以我可以逐个检查重复,但我怎么能以更简单的方式做到这一点？例如,如果MAX的值为20,该怎么办？谢谢.

int MAX = 5;

for (i = 1 , i <= MAX; i++)
{
        drawNum[1] = (int)(Math.random()*MAX)+1;

        while (drawNum[2] == drawNum[1])
        {
             drawNum[2] = (int)(Math.random()*MAX)+1;
        }
        while ((drawNum[3] == drawNum[1]) || (drawNum[3] == drawNum[2]) )
        {
             drawNum[3] = (int)(Math.random()*MAX)+1;
        }
        while ((drawNum[4] == drawNum[1]) || (drawNum[4] == drawNum[2]) || (drawNum[4] == drawNum[3]) )
        {
             drawNum[4] = (int)(Math.random()*MAX)+1;
        }
        while ((drawNum[5] == drawNum[1]) ||
               (drawNum[5] == drawNum[2]) ||
               (drawNum[5] == drawNum[3]) ||
               (drawNum[5] == drawNum[4]) )
        {
             drawNum[5] = (int)(Math.random()*MAX)+1; …

说我有一个长度数字的链表N.N非常大,我事先并不知道确切的价值N.

如何最有效地编写一个从列表中返回k完全随机数的函数？

说我有y不同的值,我想x随机选择它们.这样做的有效算法是什么？我可以打电话给rand() x时间,但如果很大x,表现会很差y.

请注意,此处需要组合:每个值应具有相同的概率,但结果中的顺序并不重要.当然,任何生成排列的算法都是合格的,但我想知道如果没有随机顺序要求,是否可以更有效地做到这一点.

如何有效地生成0和上限N之间的K个非重复整数的列表,涵盖了这种情况的排列.

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

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

int vektor[10];   

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

//No uniqueness here

我知道几个例程如下:

X _{n + 1} =例程(X _n,max)

例如,类似于LCG发生器:

X _{n + 1} =(a*X _n + c)mod m

此生成器中没有足够的参数化来生成每个序列.

梦想功能:

X _{n + 1} =例程(X _n,max,置换数)

该例程通过索引到所有排列集合中进行参数化,将返回序列中的下一个数字.序列可以是任意大的(因此存储阵列并使用事实数字是不切实际的.

如果失败了,是否有人指向类似的函数,这些函数要么是无状态的,要么具有任意"max"的恒定状态,这样它们就会迭代一个混洗列表.

我正在寻找生成伪随机数[可能是低"随机性"]或具有固定汉明权重[固定密度为1s]的伪随机比特序列的方法.我发现了一些关于使用简单的线性同余生成器和一个具有我需要的汉明重量的种子的建议,但没有给出为什么这是正确的原因[为什么汉明重量在线性同余变换下是不变的]

任何人都可以说明这一点或给我另一种方式吗？

谢谢...

可能重复:
O(1)中的唯一(非重复)随机数？
如何有效地生成0和上限N之间的K个非重复整数列表

我想在某个diapason中生成随机数,我必须确定,每个新数字都不是前者的副本.一种解决方案是将以前生成的数字存储在容器中,并且每个新数字都检查容器.如果容器中有这样的数字,那么我们生成agin,否则我们使用并将其添加到容器中.但是对于每个新的数字,这个操作变得越来越慢.有没有更好的方法,或任何可以更快地工作并确保代的唯一性的兰特函数？

编辑:是的,有一个限制(例如从0到1.000.000.000).但我想生成100.000个唯一数字!(如果解决方案是使用Qt功能,将会很棒.)

假设我有一系列数字:{n,n + 1,n + 2,... n + m}

如果不提前存储数字,我想创建一个函数f(),给定序列{1,2,3,... m}将以随机(或至少伪随机)顺序吐出原始集合.

例如假设我的序列是{10,11,12,13,14,15,16,17}

   f(1) could yield 14
   f(2) could yield 17
   f(3) could yield 13
   f(4) could yield 10
   f(5) could yield 16
   f(6) could yield 15
   f(7) could yield 11
   f(8) could yield 12

在过去的某个时刻,一位同事向我展示了一种能够做到这一点的数学算法,但是我已经忘记了除了存在之外几乎所有关于它的事情.我记得你必须事先得到序列,并从函数中使用的序列中生成一些常量.对于那些想知道的人,我遗憾地失去了与那位同事的联系.

这个问题的答案看起来很接近我想要的,但我不确定答案是否允许我提前将输出约束到特定序列.

编辑:

为了澄清一点,我不想存储原始序列或混洗序列.我想从原始序列生成函数f().

令人沮丧的是,我已经看到了这一点,我只是记不起来,谷歌再次找到它.

Fisher-Yates算法非常适合置换或改组卡座,但它不是我想要的.

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

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

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

如何生成随机整数但确保它们不会重复？

现在我使用:

Random randomGenerator = new Random();
randomGenerator.nextInt(100);

EDIT I

我正在寻找最有效的方式,或者最不好的方式

EDIT II

范围并不重要

假设我想生成从ArrayList中获取的随机数:(1,2,3,4,5,6,7,8,9,10)

随机生成器产生5.

列表更新 - AL:(1,2,3,4,6,7,8,9,10)

下一个随机数不能是5.

我正在编写一个从arraylist生成随机数的程序,一旦生成随机数,列表就会删除该数字,下一个随机生成的数字不能是该数字.

ArrayList<Integer> numsLeft = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9,10));

  Random randomGenerator = new Random();

 int number = 0; 
 String cont;

 do
 {
 number = randomGenerator.nextInt(numsLeft.size()); 
 numsLeft.remove(number);

  System.out.println (number + " continue (y/n)");
  cont = (stdin.readLine());
 } 
 while (cont.equalsIgnoreCase("y"));      

但我唯一可以做的就是减小尺寸......

http://docs.oracle.com/javase/7/docs/api/java/util/Random.html

可能重复:
创建无重复的随机数序列

我想写一个只使用数字作为短字符串的URL缩短器.

我不想数数,我希望下一个新数字是随机的(或伪随机).

首先,思想算法看起来像这样(伪代码):

do 
{
 number = random(0,10000)
}
while (datastore.contains(number))

datastore.store(number, url)

此实现的问题是:由于数据存储区包含更多数字,因此循环将多次执行的可能性越大.性能会随着时间的推移而降低.

是否有更好的方法来获取尚未使用的随机数？