Python: 以低成本生成大型均匀排列

Question

Python: 以低成本生成大型均匀排列

4

我不确定这个理论上是否可能；但如果可以，我想知道如何在Python中实现。我想要以低成本生成大型随机排列。例如，假设我想要在range(10**9)上进行一个排列。我希望该排列是均匀的（即我希望数字分散在各处，没有任何明显的结构）。我希望有一个函数可用于获取每个n处的排列项，并且我希望有另一个函数可用于获取排列中每个数字的索引。最终的重要条件是：我希望在不必存储所有排列项的情况下完成所有操作。（这可能需要大量空间。）我希望每个项都可以访问，但我不希望像Python 3中的range那样存储所有项。是否可能？

- Ram Rachum

1

我想多了解一下这个应用程序。到底是什么阻止你只使用范围内的随机整数呢？ - Slater Victoroff

2

我不认为在排列方面做这件事有太大的希望。仅仅存储你选择的10^9!个排列中的哪一个就需要超过10 GiB，这是通过http://en.wikipedia.org/wiki/Stirling%27s_approximation#Versions_suitable_for_calculators中的ln n!近似计算得出的--再加上没有可行的PRNG具有足够长的周期来生成这些排列的相当一部分，这意味着你只能选择一个微小的、规则的排列子集。另一方面，如果你只想要range(10**9)中的一些（唯一的？）数字... - user395760

线性反馈移位寄存器可以拥有非常大的周期，并以看似随机的顺序生成每个数字。 - grasshopper

现在我想起来了，像AES这样的分组密码难道不正好符合这个要求吗？ - Ram Rachum

2个回答

1

我相信像AES这样的分组密码算法可以提供这种功能。

- Ram Rachum

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- grasshopper · Accepted Answer

我能想到的唯一实现方式并部分满足您的要求，是排列不是随机的但看起来随机，并且实际上是一系列数列，如果你知道a_n-1，就可以生成a_n。

请看这个链接：http://en.wikipedia.org/wiki/Linear_feedback_shift_register 你需要的是最大长度LSFR。它将以看似随机的顺序生成0到2 ** n-1的所有数字。对于不同的n，您需要使用不同的函数。

然而，我认为您不能有getIdxOf（val）和getValOf（Idx）这样的函数，除非您只是一个接一个地通过生成函数。