检索伪随机序列的已知索引

Question

我有一套16,704,200件独特的物品。我需要构造一个函数f，以便：

• f(x)从列表中返回一个看似随机的对象(但对于给定的x值总是相同的对象)
• f(0)通过f(16704199)以看似随机的顺序返回完整的对象集(不重复)
• f不需要存储16,704,200个有序整数的列表

我看过几个关于使用伪随机数发生器或线性反馈移位寄存器来产生随机数序列的答案。缺点是找到f(7000)值的唯一方法是初始化寄存器，循环7000次，然后返回数字。(除非我存储了整个预先生成的序列，正如上面所述，我不想这样做。)

有什么算法更适合在随机序列中找到第7000次(xth)条目吗？

Answer 1

您可以使用线性同余发生器 -这种类型的PRNG现在被认为是非常粗糙的，对于任何需要统计随机性的目的来说，但是在您的情况下，它确实有一个优势，它可以重复一个已知大小的特定序列。它也是可逆的，这与您对序列id和所选索引id之间的1到1映射的要求有关。

首先，选择几个素数，介于60%到80%的总尺寸N之间。

N = 16_704_200
A =  9_227_917
C = 11_979_739

您可以使用素数模块来查找您的数字。您甚至可以使用PRNG来选择它们，并且只存储所需的素数。

现在您有了这些值，您可以实现LCG算法，这是您想要的f(x)

def lcg x
  ( A * x + C ) % N
end

快速测试：

lcg( 0 )
# => 11979739

lcg( 12345 )
# => 7971104

(0..9).map { |x| lcg( x) }
 # => [ 11979739, 4503456, 13731373, 6255090, 15483007,
 #      8006724, 530441, 9758358, 2282075, 11509992 ]

。。。它可能是随机的，如果您反馈输出作为下一个输入参数，那么您就有了一个“老派”(而且质量很低) PRNG。但是您可以使用它作为index_id = lcg( sequence_id )，以随机的方式获取对象。

它是否将整组输入值映射到同一组输出值：

(0...N).map { |x| lcg( x ) }.uniq.count
# => 16704200

是!

虽然你不需要它，但算法是可以逆转的。以下是如何做到这一点：

棘手之处在于计算出A的乘法逆。下面是我找到的一个如何做的例子。

AINVERSE = 9257653
# Test it:
( A * AINVERSE ) % N 
# => 1

现在您有了这些值，您可以前后执行LCG算法：

def lcg_fwd x
  ( A * x + C ) % N
end

def lcg_rev x
  ( AINVERSE * ( x - C ) ) % N
end

测试它：

lcg_fwd( 0 )
# => 11979739
lcg_rev( 11979739 )
# => 0

lcg_fwd( 12345 )
# => 7971104
lcg_rev( 7971104 )
# => 12345

Answer 2

也许一个预先播种的随机对象可以起作用吗？

prng1 = Random.new(1234)
prng1.seed       #=> 1234
prng1.rand(100)  #=> 47
prng1.rand(99)   #=> 83

prng2 = Random.new(prng1.seed)
prng2.rand(100)  #=> 47
prng2.rand(99)   #=> 83

http://www.ruby-doc.org/core-2.1.1/Random.html

如果选择足够大的值，就会得到唯一的数字：

(1..1_000_000).map {|i| prng1.rand(1_000_000_000_000+i)}.uniq.size
=> 1000000