在python中寻找一种简单有效的生成随机数的方法，这样每10个数字序列中的数字就不会重复

Question

我想知道是否有一种简单有效的方法可以在python中生成随机数 所以每10个序列都是不同的数字

我尝试了这个选项：

import random
random.randint(0,100)

但几代人之后，我注意到生成的数字可以一个接一个地重复 所以我试着用一组这些数字解决了这个问题 但它会留下一些数字，如果我需要特定数量的随机生成的数字，我需要在之后重新生成这些数字，但过了一段时间，有人建议我使用另一种解决方案：

Randlist = random.sample(range(1,101), k=10)

这很好，但是需要一个整数列表来保存我的10个不同的数字

有没有一种方法可以在没有列表的情况下完成它，这样它就不会像O（n^2）或以上那样太复杂

Answer 1

算法

import random

def randoms():
    while True:
        yield random.randint(0,9)

def no_repeat(source_iter, length):
    seen = set()
    cycle_pos = 0
    while True:        
        n = next(source_iter)
        if n not in seen:
            yield n
            cycle_pos += 1
            seen.add(n)

            if cycle_pos == length:
                seen.clear()
                cycle_pos = 0


rep = no_repeat(randoms(), 10)

print([next(rep) for i in range(100)]) # take 100 items from the `rep` iterator and put them into a list

randoms函数是一个生成器，它给出无限个随机数。 no_repeat函数是一个生成器，它将生成器作为参数并对其进行过滤，以便长度为10的每个部分都没有重复

通过组合这些生成器，可以生成一个迭代器，该迭代器在每个长度为10的序列中生成无重复的随机数

复杂性

如果您假设可能的随机数的范围远大于“周期长度”，则生成O(n)个数是n，因为每次迭代都会生成一个随机数，生成它，并将其添加到集合中。假设集合是一个哈希表，那么这个加法是O(1)（检查它是否在集合中也是如此）。如果清除一个集合是O(n)，那么如果每10个操作执行一次，并且所需时间与10成比例，那么这将分摊到每次迭代的O(1)

如果要考虑更小范围的可能数字，那么对于循环长度k，在循环开始时，每次迭代O(1)，则存在冲突的1/k概率，然后对于下一次迭代2/k概率等，直到在k迭代后重置。 因此它是O(k^2 n)，但是这个k是固定的（在你的例子中它总是10），所以实际上它可以被认为是一个常数因子，使得它等价于O(n)