1

我正在寻找一种有效的算法，它可以在一定范围内产生随机值，而不会重复。

在伪代码中：（在 Rand 类中）

  Rand(long from, long to) {
    this.from = from;
    this.to = to;
    // ...
  }

  long getNumber() {

    // returns a random number in the [from, to] range
    //  which has never been returned before
  }

用法：

  Rand r = new Rand(1, 100000000);

  long x = r.getNumber();
  long y = r.getNumber();
  ...

从 r.getNumber() 返回的数字应始终与先前返回的数字不同。
当然，如果to - from + 1返回了数字，算法应该重新开始（或者出错 - 无论如何都不重要）。

请注意，范围可能非常大，因此随机排列的数组（包含初始[from, to]数字）可能会溢出内存。

4

7 回答 7

5

密码是一对一的映射，否则无法解密。因此，任何块密码都会将数字 0、1、2、3、4、5……映射到不同的 n 位数，其中 n 是密码的块大小（以位为单位）。

将一个简单的 4 轮 Feistel 密码与您想要的任何（偶数）块大小组合在一起相对容易。只有四轮它会很快但不安全。或者使用Hasty Pudding 密码，它可以有几乎任何你想要的块大小。

无论您使用什么密码，只需加密数字 0、1、2……并查看输出块。您可以丢弃任何超出您要求范围的结果，并且所有结果都保证是唯一的。

于 2011-08-19T12:09:39.233 回答
1

一种方法是生成一个介于 from 和 to 之间的数字列表，随机删除这些数字，直到袋子为空，然后重新填充。为了节省大范围的存储空间，您可以将拾取的数字记录到一个点（选择重复时重新拾取），因为最初拾取重复的概率应该很低。确定最佳过渡点可能是一项经验练习。

编辑：还有一些想法。

对于真正巨大的范围，即使在内存限制下也无法提供良好的性能。一种想法可能是将候选对象存储为不作为数字列表，而是作为间隔。因此，最初，您在 from 和 to 之间进行选择，得到 x1。下一次，从第一个子区间或第二个子区间中选择一个数字，概率与区间长度成正比。在每一步，消除长度为零的区间。这需要存储 M + 2 个整数（在最坏的情况下），其中 M 是抽奖次数，或者 N/2 渐近地用于大 N（在最坏的情况下），其中 N 是初始间隔大小。不过，有人可能会仔细检查我。

于 2011-08-19T03:33:27.890 回答
1

如果您不需要间隔中的每个数字最终出现，您可以使用线性同余生成器：

int getNumber() {
    seed = (seed * A + C) mod (to-from);
    return seed + to;
}

它是周期性的，当种子等于初始值时，新的周期开始，周期的长度取决于 A 和 C 的选择。

优点：O(1) 时间和空间，缺点：并非间隔中的每个数字都会出现。

对于长度为 2^m 的间隔，请查看http://en.wikipedia.org/wiki/Linear_feedback_shift_register我没有使用它，但维基百科说它可能是最大长度，即你可以拥有所有数字（除了一个）出现在输出中。

于 2011-08-19T04:34:57.093 回答
1

一些想法作为一个起点：

1) 假设您有一个函数 f(x)，它是 1..N 上的一个排列，其中 N 大于您的范围。如果将其应用于范围内的 x，它可能会产生非法值 - 超出范围。您可以通过在非法值上再次调用 f 来定义范围内的排列。你最终会得到一个合法的值，因为序列 x、f(x)、f^2(x)、f^3(x) 最终必须循环，如果最坏的情况出现在最坏的情况下，它将在 x 处返回。

2) 有交换网络允许您为特殊 N 生成 N 个对象的所有可能排列 - 一个示例是http://en.wikipedia.org/wiki/Clos_network#Bene.C5.A1_network_.28m_.3D_n_.3D_2。 29（有趣的 URL - Benes 网络）。您可以通过随机设置开关来获得 N 个对象的任意排列，其中 N 可能我认为必须是 2 的幂。由于会有 K 个开关，因此有 2^K 种设置它们的方法，这意味着您没有 M！等概率排列，但也许你不会介意这一点，或者可以通过重复多次或其他方式来最小化非随机性。

3）如果您准备通过多次应用许多不同的基本排列来实现接近随机性，您可以尝试在整个范围内交替添加 mod N，然后将范围拆分为子范围，例如一些 p-1 值在该范围内应用通过乘以某个 k 模式 p 产生的排列。希望是，尽管通过应用足够多的步骤并使它们足够多样化，每个单独的步骤都是非常基本的，但结果将接近随机，特别是如果您随机选择参数。

于 2011-08-19T06:03:20.310 回答
1

你可以这样进行（在python中）：

创建一个 xrange 并从中选择 k 个随机元素并将其用作 RandomGenerator：

import random

def randomFromTo(FROM,TO,k): #k is the number of sample you want to generate
    m= random.sample(xrange(FROM,TO),k)
    return (i for i in m)

您的生成器将随机生成从 FROM 到 TO 的所有数字，并在生成超过 k 个数字时失败：

通过这个例子，你会得到：

RandomGenerator=randomFromTo(10,1000000000,12)

for k in range(12): 
    print RandomGenerator.next()

你得到

57625960
50621599
2891457
56292598
54608718
45258991
24112743
55282480
28873528
1120483
56876700
98173231
于 2011-08-19T10:35:32.413 回答
1

我会假装你在 R 中寻求解决方案（根据标签）。您正在尝试做的是无需更换的样品。在 R 中，有一个名为sample. 在这里，我正在对一个包含 30 个值（1、2、3...30）的向量进行采样，并且一旦我绘制了一个数字，它就不会被替换。您可以通过设置种子（请参阅 参考资料set.seed）使其在其他机器上可重现。

我运行了很多次以显示随机性。

> sample(x = 1:30, size = 10, replace = FALSE)
 [1]  9 16 13 20 12  3  1  5 28  7
> sample(x = 1:30, size = 10, replace = FALSE)
 [1] 22 11 26 29 20  1  3  6  7 10
> sample(x = 1:30, size = 10, replace = FALSE)
 [1]  1 11 16  7 22 26  3 25  8  9
> sample(x = 1:30, size = 10, replace = FALSE)
 [1]  7 17  3 22 21 24 27 12 28  2
> sample(x = 1:30, size = 10, replace = FALSE)
 [1] 30 21 23  2 27 24  3 18 25 19
> sample(x = 1:30, size = 10, replace = FALSE)
 [1]  4  6 11 16 26  8 17 22 23 25
于 2011-08-19T11:42:15.433 回答
1

@rossum 说：

密码是一对一的映射，否则无法解密。因此，任何块密码都会将数字 0、1、2、3、4、5……映射到不同的 n 位数，其中 n 是密码的块大小（以位为单位）。

因此，即使是异或加密或按位反转也可以用于某些目的。

这是一个使用 xor 和按位反转作为简单的一对一加密的 php 函数。

它是一个伪随机数生成器，保证填写所有值并且没有相同的值。您提供 n:0..63，它提供随机的 0..63。

它只接受 2^i 范围，如 0..63、0..127 等。

不是密码安全等，只是随机的。

这样的函数非常适合垃圾收集例程，因为它不会尝试两次清理同一区域，即使是随机执行的操作。

 function math_random_filled($n,$bits,$seed)
 {
   //bits: examples: 6=0..63, 8=0..255, 10: 0..1023
   //n: 0<= n <2^$bits
   //seed: any string or number

   //generate xor: crc32 + bit mask
   $xor= crc32($seed.'internalseed') & ~(-1<<$bits);
   //xor
   $r=intval($n)^$xor;
   //bitwise reverse
   $r=bindec(strrev(str_pad(decbin($r),$bits,'0',STR_PAD_LEFT)));
   return $r;
 }

 //demonstration
 $bits=6;
 $min=0;
 $max=pow(2,$bits)-1;
 $count=$max-$min+1;
 for($n=0;$n<=$max;$n++)
 {
   $r=math_random_filled($n,$bits,$seed='someseed');
   echo " $r ";
   $ar[$r]=1;
 }


 $set=0;
 for($n=0;$n<=$max;$n++)
   if(isset($ar[$n])) $set++;


 echo "\n"."bits: $bits,  count: $count, set: ". $set."\n\n";

示例输出：

 37  5  53  21  45  13  61  29  33  1  49  17  41  9  57  25  39  7  55  23  47  15  63  31  35  3  51  19  43  11  59  27  36  4  52  20  44  12  60  28  32  0  48  16  40  8  56  24  38  6  54  22  46  14  62  30  34  2  50  18  42  10  58  26 

bits: 6,  count: 64, set: 64

您可以在 php 沙箱中测试此处的代码

这是另一个，但接受任何范围，不仅是 2 的幂。

function math_random_filled_arithmetical($n,$max,$seed)
    {
    /*
    - produces 0..max, repeatable, unique, one-to-one mapped random numbers
    - uses arithmetic operations to imitate randomness
    - $n: 0<=$n=<$max
    - $max: any integer, not only power of two
    - $seed: any string or number
    */
    $n=intval($n);
    $max=intval($max);
    $opt1=$n;
    $opt2=$max-$n;
    $n2=min($opt1,$opt2);
    $reverseit=crc32($seed.'internalseed'.$n2)&1;
    if($opt1>$opt2) $reverseit=!$reverseit;
    $max2=floor(intval($max-1)/2);
    //echo "n:$n, max:$max,n2:$n2,max2:$max2,reverseit:$reverseit\n";
    if($max>=3)
    if($opt1!=$opt2)
        $n2=math_random_filled_arithmetical($n2,$max2,$seed.'*');
    $res=$reverseit? $max-$n2:$n2;
    $res=intval(fmod($res+(crc32($seed)&(1<<30)),$max+1));
    //echo "n:$n, max:$max, res:$res\n";
    return $res;
    }


//demonstration
$max=41;//-- test a max value 
for($n=0;$n<=$max;$n++)
    {
    $r=math_random_filled_arithmetical($n,$max,$seed='someseed');
    $ar[$r]=1;
    echo " $r ";
    }
$filled=0;
for($n=0;$n<=$max;$n++)
    if(isset($ar[$n])) $filled++;
echo "\n count: ".($max+1).", filled: ". $filled."\n";

示例输出：

 20  19  18  17  33  32  37  36  14  13  31  34  35  26  16  11  12  3  39  40  0  41  1  2  38  29  30  25  15  6  7  10  28  27  5  4  9  8  24  23  22  21 
 count: 42, filled: 42

相关的php沙箱在这里

于 2013-04-08T04:04:47.150 回答