algorithm - 从非常大的集合中生成看似随机排列而不重复的有效方法？

Question

我有一个非常大的集合(十亿 或更多，预计会呈指数增长到某个水平)，我想从中生成看似随机的元素而不重复。我知道我可以选择一个随机数并重复并记录我生成的元素，但是随着数字的生成，这会占用越来越多的内存，并且在输出几百万个元素后就不实用了。

我的意思是，我可以说 1、2、3 直到十亿，每个都是常数时间而无需记住之前的所有，或者我可以说 1、3、5、7、9 和然后是 2、4、6、8、10，但是否有更复杂的方法来做到这一点并最终获得该集合的看似随机排列？

更新

1、集合在生成过程中不改变大小。我的意思是当用户的输入线性增加时，集合的大小呈指数增加。

2、简而言之，集合就像是从1到100亿或更多的每一个整数的集合。

3、总的来说，上百亿是因为每个元素都携带了很多独立选择的信息，比如。想象一个 RPG 角色有 10 个属性，每个属性可以从 1 到 100(对于我的问题，不同的选择可以有不同的范围)，因此有 10^20 个可能的字符，数字“10873456879326587345”将对应一个具有“11， 88、35...”，我想要一种算法来一个一个地生成它们而不重复，但让它看起来是随机的。

Answer 1

感谢您提出有趣的问题。您可以使用模幂创建几个字节的“伪随机”*(循环)排列。假设我们有 n 个元素。搜索大于 n+1 的素数 p。然后找到原根 g 模 p。基本上根据原根的定义， Action x --> (g * x) % p 是 {1, ..., p-1} 的循环排列。所以 x --> ((g * (x+1))%p) - 1 是 {0, ..., p-2} 的循环排列。如果它给出的值大于(或等于)n，我们可以通过重复先前的排列来获得 {0, ..., n-1} 的循环排列。

我将这个想法实现为一个 Go 包。 https://github.com/bwesterb/powercycle

package main

import (
    "fmt"
    "github.com/bwesterb/powercycle"
)

func main() {
    var x uint64
    cycle := powercycle.New(10)
    for i := 0; i < 10; i++ {
        fmt.Println(x)
        x = cycle.Apply(x)
    }
}

这会输出类似的东西

0
6
4
1
2
9
3
5
8
7

但这可能会因所选择的发电机而有所不同。

速度很快，但不是特别快:在我用了 5 年的 i7 上，计算 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000了了一个循环的一个应用程序只需要不到 210ns 的时间。更多详情:

BenchmarkNew10-8                     1000000          1328 ns/op
BenchmarkNew1000-8                    500000          2566 ns/op
BenchmarkNew1000000-8                  50000         25893 ns/op
BenchmarkNew1000000000-8              200000          7589 ns/op
BenchmarkNew1000000000000-8             2000        648785 ns/op
BenchmarkApply10-8                  10000000           170 ns/op
BenchmarkApply1000-8                10000000           173 ns/op
BenchmarkApply1000000-8             10000000           172 ns/op
BenchmarkApply1000000000-8          10000000           169 ns/op
BenchmarkApply1000000000000-8       10000000           201 ns/op
BenchmarkApply1000000000000000-8    10000000           204 ns/op

为什么我说“伪随机”？好吧，我们总是在创建一种非常特殊的循环:即使用模幂的循环。不过它看起来很伪随机。