python - 在集合中查找可用的 "spots"

Question

我正在寻找一种以编程方式在列表中查找可用(未使用)位置的方法，通常是一组条件。我可以给你一个电话簿的例子:我将生成具有特定规则的电话号码(例如，在本例中为 7 位数字，这非常简单)。 “生成器”将随机选择一个可用的数字。下一次尝试时，该数字将不会出现在生成器中。

generator = PhoneNumberGenerator()
generator.generate()
"559-608-XXXX"
# This number won't be available next time the generator.generate is called

一种可能性是将“使用过的”电话号码存储在排序列表中，并查找第一个可用的可能性。但这不会是非常随机的。第一个生成的数字为 000-0000，第二个为 000-0001，依此类推。另一种可能性是创建所有可用电话号码的完整列表并删除已使用的电话号码，但这将是一个巨大的列表。假设经常使用生成器，性能可能会受到影响。

当然，我在这里使用电话号码生成器的示例，但这可能是不同的生成器，用于车牌或验证码或其他任何内容，只是由一组规则定义。我正在尝试用 Python 来做到这一点，所以欢迎使用这种语言的示例，但是如果您有其他语言的理论文章，也不要犹豫，我将编辑问题以包含答案，如果我可以。

提前致谢，

Answer 1

取两个素数，p和q ，并生成数字 p * i % q对于 0 <= i < q 。所得数字涵盖 0 中的所有数字至q (独家)以看似伪随机*的顺序，没有重复或丢失的数字。

>>> p, q = 7, 11
>>> [p*i % q for i in range(q)]
[0, 7, 3, 10, 6, 2, 9, 5, 1, 8, 4]
>>> sorted(_)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

>>> p, q = 101, 131
>>> [p*i % q for i in range(q)]
[0, 101, 71, ..., 60, 30]
>>> Counter(_).most_common(5)
[(0, 1), (1, 1), (2, 1), (3, 1), (4, 1)]

证明(不是很严格):假设列表中有重复的数字，即有 i和k这样p*i % q == p*k % q 。这意味着差异，p*(k-i) ，必须是 q 的倍数(因为它们等于模 q )，也是 p 的倍数。但如p和q是素数，它们的最小公倍数是p*q ， i < q 永远无法达到这一点。因此，列表中的所有数字必须是唯一的，并且列表有 q元素，它必须包含 0 中的所有数字至q (独家)。

显然，对于电话号码等，素数会大得多，但是(假设没有溢出等)同样的工作应该没有显着的计算或内存开销。如果您想生成特定间隔内的数字，例如 100000至999999 ，您可以选择素数，这样 q略大于数字数量，将最小值添加为每个数字的偏移量，并删除所有大于上限的数字。另外，用前导零填充数字。

<小时/>

*) 当然，这不是随机的，甚至不是伪随机的，只是根据数字不能出现两次的标准，并且很容易算出下一个数字。但对于“随意”的观察者来说，它们应该显得足够随机，无法确定两个数字中的哪一个首先生成，或者在某个给定数字之前生成了多少个数字。