如何随机迭代一个大范围？

Question

我想随机迭代一个范围.每个值只访问一次,最终将访问所有值.例如:

class Array
    def shuffle
        ret = dup
        j = length
        i = 0
        while j > 1
            r = i + rand(j)
            ret[i], ret[r] = ret[r], ret[i]
            i += 1
            j -= 1
        end
        ret
    end
end

(0..9).to_a.shuffle.each{|x| f(x)}

哪个f(x)是对每个值进行操作的函数.一个费雪耶茨洗牌用于有效地提供随机排序.

我的问题是shuffle需要在阵列上操作,这并不酷,因为我正在使用天文数字大的数字.Ruby会快速消耗大量的RAM,试图创建一个怪异的数组.试想一下,替换(0..9)用(0..99**99).这也是以下代码不起作用的原因:

tried = {} # store previous attempts
bigint = 99**99
bigint.times {
    x = rand(bigint)
    redo if tried[x]
    tried[x] = true
    f(x) # some function
}

这段代码非常天真,并且因为tried获得更多条目而快速耗尽内存.

什么样的算法可以完成我想要做的事情？

[Edit1]:我为什么要这样做？我试图耗尽哈希算法的搜索空间,寻找一个寻找部分冲突的N长度输入字符串.我生成的每个数字等同于唯一的输入字符串,熵和全部.基本上,我正在使用自定义字母 "计数" .

[Edit2]:这意味着f(x)在上面的示例中是一种生成散列并将其与常量目标散列进行比较的方法,以用于部分冲突.x在调用之后我不需要存储值,f(x)因此内存应该随时间保持不变.

[Edit3/4/5/6]:进一步澄清/修正.

[解决方案]:以下代码基于@ bta的解决方案.为简明起见,next_prime未显示.它产生可接受的随机性,并且只访问每个数字一次.有关详细信息,请参阅实际帖子.

N = size_of_range
Q = ( 2 * N / (1 + Math.sqrt(5)) ).to_i.next_prime
START = rand(N)

x = START
nil until f( x = (x + Q) % N ) == START # assuming f(x) returns x

Answer 1

我只记得几年前我上过的一个类似的问题; 也就是说,在给定非常严格的内存约束的情况下,通过集合(相对)随机迭代(完全耗尽它).如果我正确记住这一点,我们的解决方案算法是这样的:

1. 将范围定义为从0到某个数字 N
2. x[0]在里面生成一个随机起点N
3. 生成Q小于的迭代器N
4. x[n]通过添加Q到前一个点并在需要时环绕来生成连续点.那是,x[n+1] = (x[n] + Q) % N
5. 重复,直到生成一个等于起点的新点.

诀窍是找到一个迭代器,它可以让你遍历整个范围而不会产生两次相同的值.如果我记得正确的,任何相对素N和Q将工作(越接近越少"随机"的输入范围的边界数).在这种情况下,不是因素的素数N应该起作用.您还可以在结果数字中交换字节/半字节,以更改生成的点"跳转"的模式N.

该算法仅需要存储起始点(x[0]),当前点(x[n]),迭代器值(Q)和范围限制(N).

也许其他人记得这个算法,可以验证我是否正确记住它？